Research output per year
Research output per year
Alessio Chiapperini, Marino Miculan, Marco Peressotti^{*}
Research output: Contribution to journal › Journal article › Research › peer-review
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 language | English |
---|---|
Article number | 102842 |
Journal | Science of Computer Programming |
Volume | 221 |
Number of pages | 31 |
ISSN | 0167-6423 |
DOIs | |
Publication status | Published - 1. Sept 2022 |
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review