Back to search

University of Glasgow

Efficient and scalable algorithms for bigraph matching

Abstract

dc:description.abstract

Bigraph reactive systems provide an established approach to modelling large and dynamic systems which contain both spatial and non-spatial relationships between entities, and have been used for modelling in a wide variety of research areas such as biology, networking, sensors and security. Bigraph state rewriting operations which represent temporal evolution rely upon an underlying NP-complete matching algorithm to identify pattern components to substitute, but this limits the scale and scope of bigraphs due to the computational cost and frequency of rewriting. The bigraph matching tool BigraphER relies on a Boolean satisfiability (SAT) encoding to do this, which generates an impractically large number of clauses for larger models which limits scalability and is difficult to adapt for extensions to the bigraph structure. We propose a novel and efficient algorithm for solving bigraph matching which encodes the problem as a subgraph isomorphism constraint satisfaction problem, applying additional constraints where required to model the added complexity of bigraph composition logic. This approach can be supported by any constraint programming toolkit as well as any graph solving tool which supports additional side-constraints. This approach also grants more flexibility in regards to modelling extensions to the bigraph formalism such as bigraphs with sharing and directed bigraphs. We adapt the state of the art constraint-based Glasgow Subgraph Solver tool to implement the encoded matching problem, where we observe a greater solve time of over two orders of magnitude on a variety of different real-world matching instances performed within mixed reality, protocol and conference models. We also integrate the subgraph solver into the BigraphER framework and provide further evaluation metrics when used as a component for building full-scale models. We build further upon this idea by proposing an adaptation for the McSplit algorithm for finding largest common subgraphs in order to obtain a maximum common bigraph between two agents, a novel definition which provides the means for supporting more rich and complex types of modelling in a bigraph toolkit such as performing contextual transitions for labelled transition systems and identifying bisimulations. This is implemented using a prototype solver to demonstrate the promise of this approach. These contributions substantially expand the scope of bigraph modelling tools and their applications for modeling large-scale systems.

Degree

thesis:*
Level dc:type.qualificationlevel
PhD
Grantor dc:publisher.institution
University of Glasgow
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Burns, Kyle

Subjects

dc:subject × 1

Rights

Language dc:language
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
University of Glasgow
Base URL
theses.gla.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Burns, Kyle. Efficient and scalable algorithms for bigraph matching. PhD thesis, University of Glasgow, 2025. https://doi.org/10.5525/gla.thesis.85146