Computing (optimal) embeddings of directed bigraphs

Alessio Chiapperini, Marino Miculan, Marco Peressotti*


Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

11 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.

TidsskriftScience of Computer Programming
Antal sider31
StatusUdgivet - 1. sep. 2022

Bibliografisk note

Publisher Copyright:
© 2022 The Author(s)


Dyk ned i forskningsemnerne om 'Computing (optimal) embeddings of directed bigraphs'. Sammen danner de et unikt fingeraftryk.
  • 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. (red.). Springer, s. 38-56 (Lecture Notes in Computer Science, Bind 12150).

    Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

    Åben adgang