STAF 2025
Tue 10 - Fri 13 June 2025 Koblenz, Germany

Bigraph reactive systems offer a powerful and flexible mathematical framework for modeling both spatial and non-spatial relationships between agents, with practical applications in domains such as smart technologies, networks, sensor systems, and biology. While bigraphs theoretically support the identification of bisimilar agents by simulating and comparing their corresponding minimal contextual transition systems, no known algorithm exists for computing the maximum shared structure between two bigraphs, an essential prerequisite for determining the set of possible transitions for a given agent state. In this work, we provide a definition of the maximum common bigraph problem, and present an adaptation of the McSplit maximum common induced subgraph algorithm to compute the maximum common bigraph between two bigraph states. Our approach opens a path toward supporting bisimulation checking in bigraph-based tools, which have been leveraged in other modeling paradigms for simplification, optimization, and verification of models.

Tue 10 Jun

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

11:00 - 12:30
GCM Session 1: Bisimulation Checking, Binary Search Trees, Model SynchronizationGCM at M 201
Chair(s): Jens Kosiol Philipps-Universität Marburg
11:00
30m
Paper
Implementing Binary Search Trees in GP2 (Work in Progress)
GCM
Detlef Plump University of York, Ziad Ismaili Alaoui University of Liverpool
File Attached
11:30
30m
Paper
Comparing Synchronization Blocks with Double Pushout Synchronization
GCM
Georg Hinkel RheinMain University of Applied Sciences, Wiesbaden, Germany
File Attached
12:00
30m
Paper
Introducing The Maximum Common Bigraph Problem
GCM
Kyle Burns University of Glasgow, Michele Sevegnani University of Glasgow, James Trimble University of Glasgow, Ciaran Mcreesh
File Attached