Computing Embeddings of Directed Bigraphs

Alessio Chiapperini; Marino Miculan; Marco Peressotti

doi:10.1007/978-3-030-51372-6_3

Computing Embeddings of Directed Bigraphs

Alessio Chiapperini, Marino Miculan^*, Marco Peressotti

^*Corresponding author for this work

Department of Mathematics and Computer Science

University of Udine

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

Directed bigraphs are a meta-model which generalises Milner’s bigraphs by taking into account the request flow between controls and names. A key problem about these bigraphs is that of bigraph embedding, i.e., finding the embeddings of a bigraph inside a larger one. We present an algorithm for computing embeddings of directed bigraphs, via a reduction to a constraint satisfaction problem. We prove soundness and completeness of this algorithm, and provide an implementation in jLibBig, a general Java library for manipulating bigraphical reactive systems, together with some experimental results.

Original language	English
Title of host publication	Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Proceedings
Editors	Fabio Gadducci, Timo Kehrer
Publisher	Springer
Publication date	2020
Pages	38-56
ISBN (Print)	9783030513719
DOIs	https://doi.org/10.1007/978-3-030-51372-6_3
Publication status	Published - 2020
Event	13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020 - Bergen, Norway Duration: 25. Jun 2020 → 26. Jun 2020

Conference

Conference	13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020
Country/Territory	Norway
City	Bergen
Period	25/06/2020 → 26/06/2020

Series	Lecture Notes in Computer Science
Volume	12150
ISSN	0302-9743

Keywords

Graph theory
Formal graph languages
Graph transformations
Complexity

Documents & Links

10.1007/978-3-030-51372-6_3

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7314702/pdf/978-3-030-51372-6_Chapter_3.pdf

2 Article in proceedings
2 Journal article

Computing (optimal) embeddings of directed bigraphs
Chiapperini, A., Miculan, M. & Peressotti, M., 1. Sept 2022, In: Science of Computer Programming. 221, 31 p., 102842.
Research output: Contribution to journal › Journal article › Research › peer-review

Open Access
File
33 Downloads (Pure)
Towards a formal model for composable container systems
Burco, F., Miculan, M. & Peressotti, M., 30. Mar 2020, 35th Annual ACM Symposium on Applied Computing, SAC 2020. Association for Computing Machinery, p. 173-175
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Distributed execution of bigraphical reactive systems
Mansutti, A., Miculan, M. & Peressotti, M., 1. Jan 2015, In: Electronic Communications of the EASST. 71, 21 p.
Research output: Contribution to journal › Journal article › Research › peer-review

Cite this

@inproceedings{268be070fb4342b582d49aa53e4ae157,

title = "Computing Embeddings of Directed Bigraphs",

abstract = "Directed bigraphs are a meta-model which generalises Milner{\textquoteright}s bigraphs by taking into account the request flow between controls and names. A key problem about these bigraphs is that of bigraph embedding, i.e., finding the embeddings of a bigraph inside a larger one. We present an algorithm for computing embeddings of directed bigraphs, via a reduction to a constraint satisfaction problem. We prove soundness and completeness of this algorithm, and provide an implementation in jLibBig, a general Java library for manipulating bigraphical reactive systems, together with some experimental results.",

keywords = "Graph theory, Formal graph languages, Graph transformations, Complexity",

author = "Alessio Chiapperini and Marino Miculan and Marco Peressotti",

year = "2020",

doi = "10.1007/978-3-030-51372-6_3",

language = "English",

isbn = "9783030513719",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "38--56",

editor = "Fabio Gadducci and Timo Kehrer",

booktitle = "Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Proceedings",

address = "Germany",

note = "13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020 ; Conference date: 25-06-2020 Through 26-06-2020",

}

Chiapperini, A, Miculan, M & Peressotti, M 2020, Computing Embeddings of Directed Bigraphs. in F Gadducci & T Kehrer (eds), Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Proceedings. Springer, Lecture Notes in Computer Science, vol. 12150, pp. 38-56, 13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020, Bergen, Norway, 25/06/2020. https://doi.org/10.1007/978-3-030-51372-6_3

Computing Embeddings of Directed Bigraphs. / Chiapperini, Alessio; Miculan, Marino; Peressotti, Marco.
Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Proceedings. ed. / Fabio Gadducci; Timo Kehrer. Springer, 2020. p. 38-56 (Lecture Notes in Computer Science, Vol. 12150).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Computing Embeddings of Directed Bigraphs

AU - Chiapperini, Alessio

AU - Miculan, Marino

AU - Peressotti, Marco

PY - 2020

Y1 - 2020

N2 - Directed bigraphs are a meta-model which generalises Milner’s bigraphs by taking into account the request flow between controls and names. A key problem about these bigraphs is that of bigraph embedding, i.e., finding the embeddings of a bigraph inside a larger one. We present an algorithm for computing embeddings of directed bigraphs, via a reduction to a constraint satisfaction problem. We prove soundness and completeness of this algorithm, and provide an implementation in jLibBig, a general Java library for manipulating bigraphical reactive systems, together with some experimental results.

AB - Directed bigraphs are a meta-model which generalises Milner’s bigraphs by taking into account the request flow between controls and names. A key problem about these bigraphs is that of bigraph embedding, i.e., finding the embeddings of a bigraph inside a larger one. We present an algorithm for computing embeddings of directed bigraphs, via a reduction to a constraint satisfaction problem. We prove soundness and completeness of this algorithm, and provide an implementation in jLibBig, a general Java library for manipulating bigraphical reactive systems, together with some experimental results.

KW - Graph theory

KW - Formal graph languages

KW - Graph transformations

KW - Complexity

U2 - 10.1007/978-3-030-51372-6_3

DO - 10.1007/978-3-030-51372-6_3

M3 - Article in proceedings

AN - SCOPUS:85088207302

SN - 9783030513719

T3 - Lecture Notes in Computer Science

SP - 38

EP - 56

BT - Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Proceedings

A2 - Gadducci, Fabio

A2 - Kehrer, Timo

PB - Springer

T2 - 13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020

Y2 - 25 June 2020 through 26 June 2020

ER -

Computing Embeddings of Directed Bigraphs

Abstract

Conference

Keywords

Documents & Links

Fingerprint

Related research output

Computing (optimal) embeddings of directed bigraphs

Towards a formal model for composable container systems

Distributed execution of bigraphical reactive systems

Cite this