A CSP implementation of the bigraph embedding problem
This work addresses a crucial problem for bigraphical reactive systems, enabling more accurate tools and extensions, though it appears incremental as it builds on existing methods.
The paper tackles the problem of bigraph embedding, which is more informative than matching by tracking component correspondences, by presenting a sound and complete algorithm based on constraint satisfaction and implementing it in the LibBig library.
A crucial problem for many results and tools about bigraphs and bigraphical reactive systems is bigraph embedding. An embedding is more informative than a bigraph matching, since it keeps track of the correspondence between the various components of the redex (guest) within the agent (host). In this paper, we present an algorithm for computing embeddings based on a reduction to a constraint satisfaction problem. This algorithm, that we prove to be sound and complete, has been successfully implemented in LibBig, a library for manipulating bigraphical reactive systems. This library can be used for implementing a wide range of tools, and it can be adapted to various extensions of bigraphs.