Computing (optimal) embeddings of directed bigraphs

Alessio Chiapperini, Marino Miculan, Marco Peressotti*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

7 Downloads (Pure)


Bigraphs and bigraphical reactive systems are a well-known meta-model successfully used for formalizing a wide range of models and situations, such as process calculi, service oriented architectures, multi-agent systems, biological systems, etc. A key problem in the theory and the implementations of bigraphs is how to compute embeddings, i.e., structure-preserving mappings of a given bigraph (the pattern or guest) inside another (the target or host). In this paper, we present an algorithm for computing embeddings for directed bigraphs, an extension of Milner's bigraphs which take into account the request directions between controls and names. This algorithm solves the embedding problem by means of a reduction to a constraint satisfaction problem. We first prove soundness and completeness of this algorithm; then we present an implementation in jLibBig, a general Java library for manipulating bigraphical reactive systems. The effectiveness of this implementation is shown by several experimental results. Finally, we show that this algorithm can be readily adapted to find the optimal embeddings in a weighted variant of the embedding problem.

Original languageEnglish
Article number102842
JournalScience of Computer Programming
Number of pages31
Publication statusPublished - 1. Sept 2022


  • Bigraphs
  • Graph rewriting systems
  • Constraint Programming
  • Weighted bigraphs


Dive into the research topics of 'Computing (optimal) embeddings of directed bigraphs'. Together they form a unique fingerprint.
  • Computing Embeddings of Directed Bigraphs

    Chiapperini, A., Miculan, M. & Peressotti, M., 2020, Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Proceedings. Gadducci, F. & Kehrer, T. (eds.). Springer, p. 38-56 (Lecture Notes in Computer Science, Vol. 12150).

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Open Access

Cite this