Introducing The Maximum Common Bigraph Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911358624202752 |
|---|---|
| author | Burns, Kyle Sevegnani, Michele McCreesh, Ciaran Trimble, James |
| author_facet | Burns, Kyle Sevegnani, Michele McCreesh, Ciaran Trimble, James |
| contents | Bigraph reactive systems offer a powerful and flexible mathematical framework for modelling 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 modelling paradigms for simplification, optimisation, and verification of models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03898 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Introducing The Maximum Common Bigraph Problem Burns, Kyle Sevegnani, Michele McCreesh, Ciaran Trimble, James Logic in Computer Science Multiagent Systems F.2.2; F.4.1 Bigraph reactive systems offer a powerful and flexible mathematical framework for modelling 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 modelling paradigms for simplification, optimisation, and verification of models. |
| title | Introducing The Maximum Common Bigraph Problem |
| topic | Logic in Computer Science Multiagent Systems F.2.2; F.4.1 |
| url | https://arxiv.org/abs/2601.03898 |