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

^*Kontaktforfatter for dette arbejde

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstrakt

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.

Originalsprog	Engelsk
Titel	Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Proceedings
Redaktører	Fabio Gadducci, Timo Kehrer
Forlag	Springer
Publikationsdato	2020
Sider	38-56
ISBN (Trykt)	9783030513719
DOI	https://doi.org/10.1007/978-3-030-51372-6_3
Status	Udgivet - 2020
Begivenhed	13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020 - Bergen, Norge Varighed: 25. jun. 2020 → 26. jun. 2020

Konference

Konference	13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020
Land	Norge
By	Bergen
Periode	25/06/2020 → 26/06/2020

Navn	Lecture Notes in Computer Science
Vol/bind	12150
ISSN	0302-9743

Dokumenter og 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

Fingeraftryk Dyk ned i forskningsemnerne om 'Computing Embeddings of Directed Bigraphs'. Sammen danner de et unikt fingeraftryk.

2 Konferencebidrag i proceedings
1 Tidsskriftartikel

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, s. 173-175
Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review
Distributed execution of bigraphical reactive systems
Mansutti, A., Miculan, M. & Peressotti, M., 1. jan. 2015, I: Electronic Communications of the EASST. 71, 21 s.
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review
Multi-agent systems design and prototyping with bigraphical reactive systems
Mansutti, A., Miculan, M. & Peressotti, M., 1. jan. 2014, Distributed Applications and Interoperable Systems - 14th IFIP WG 6.1 Int. Conference, DAIS 2014, Held as Part of the 9th Int. Federated Conf. on Distributed Computing Techn. DisCoTec 2014, Proc.. Springer VS, s. 201-208 8 s. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 8460 LNCS).
Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Citationsformater

@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. i F Gadducci & T Kehrer (red), Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Proceedings. Springer, Lecture Notes in Computer Science, bind 12150, s. 38-56, 13th International Conference on Graph Transformation, ICGT 2020 held as part of Software Technologies: Applications and Foundations, STAF 2020, Bergen, Norge, 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. red. / Fabio Gadducci; Timo Kehrer. Springer, 2020. s. 38-56 (Lecture Notes in Computer Science, Bind 12150).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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

Abstrakt

Konference

Dokumenter og links

Towards a formal model for composable container systems

Distributed execution of bigraphical reactive systems

Multi-agent systems design and prototyping with bigraphical reactive systems

Citationsformater