Top

Published in:

2020 | OriginalPaper | Chapter

Computing Embeddings of Directed Bigraphs

Authors : Alessio Chiapperini, Marino Miculan, Marco Peressotti

Published in: Graph Transformation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Confluence up to Garbage

next chapter A Categorical Semantics for Guarded Petri Nets

Bacci, G., Grohmann, D., Miculan, M.: DBtk: a toolkit for directed bigraphs. In: Kurz, A., Lenisa, M., Tarlecki, A. (eds.) CALCO 2009. LNCS, vol. 5728, pp. 413–422. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03741-2_28CrossRef

Bacci, G., Grohmann, D., Miculan, M.: A framework for protein and membrane interactions. arXiv preprint arXiv:0911.4513 (2009)

Bacci, G., Miculan, M., Rizzi, R.: Finding a forest in a tree. In: Maffei, M., Tuosto, E. (eds.) TGC 2014. LNCS, vol. 8902, pp. 17–33. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45917-1_2CrossRef

Bundgaard, M., Glenstrup, A.J., Hildebrandt, T., Højsgaard, E., Niss, H.: Formalizing higher-order mobile embedded business processes with binding bigraphs. In: Lea, D., Zavattaro, G. (eds.) COORDINATION 2008. LNCS, vol. 5052, pp. 83–99. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68265-3_6CrossRef

Burco, F., Miculan, M., Peressotti, M.: Towards a formal model for composable container systems. In: Proceedings of the SAC, pp. 173–175. ACM (2020)

Chiapperini, A., Miculan, M., Peressotti, M.: A CSP implementation of the directed bigraph embedding problem. CoRR abs/2003.10209 (2020)

Damgaard, T.C., Glenstrup, A.J., Birkedal, L., Milner, R.: An inductive characterization of matching in binding bigraphs. Form. Asp. Comp. 25(2), 257–288 (2013)MathSciNetCrossRefMATH

Damgaard, T.C., Højsgaard, E., Krivine, J.: Formal cellular machinery. Electr. Not. Theoret. Comput. Sci. 284, 55–74 (2012)MathSciNetCrossRefMATH

Faithfull, A.J., Perrone, G., Hildebrandt, T.T.: Big red: a development environment for bigraphs. Electr. Commun. EASST 61, 1–10 (2013)

10.

Gassara, A., Rodriguez, I.B., Jmaiel, M., Drira, K.: Executing bigraphical reactive systems. Discr. Appl. Math. 253, 73–92 (2019)MathSciNetCrossRefMATH

11.

Glenstrup, A.J., Damgaard, T.C., Birkedal, L., Højsgaard, E.: An implementation of bigraph matching. IT University of Copenhagen p. 22 (2007)

12.

Grohmann, D.: Security, cryptography and directed bigraphs. In: Ehrig, H., Heckel, R., Rozenberg, G., Taentzer, G. (eds.) ICGT 2008. LNCS, vol. 5214, pp. 487–489. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87405-8_41CrossRef

13.

Grohmann, D., Miculan, M.: Directed bigraphs. ENTCS 173, 121–137 (2007)MATH

14.

Grohmann, D., Miculan, M.: Reactive systems over directed bigraphs. In: Caires, L., Vasconcelos, V.T. (eds.) CONCUR 2007. LNCS, vol. 4703, pp. 380–394. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74407-8_26CrossRef

15.

Grohmann, D., Miculan, M.: Controlling resource access in directed bigraphs. ECEASST 10, 1–21 (2008)MATH

16.

Højsgaard, E., et al.: Bigraphical languages and their simulation. IT University of Copenhagen, Programming, Logic, and Semantics (2012)

17.

Jensen, O.H., Milner, R.: Bigraphs and transitions. In: ACM SIGPLAN Notices, vol. 38, pp. 38–49. ACM (2003)

18.

Krivine, J., Milner, R., Troina, A.: Stochastic bigraphs. Electr. Not. Theor. Comput. Sci. 218, 73–96 (2008)CrossRefMATH

19.

Mansutti, A., Miculan, M., Peressotti, M.: Distributed execution of bigraphical reactive systems. ECEASST 71, 1–21 (2014)

20.

Mansutti, A., Miculan, M., Peressotti, M.: Multi-agent systems design and prototyping with bigraphical reactive systems. In: Magoutis, K., Pietzuch, P. (eds.) DAIS 2014. LNCS, vol. 8460, pp. 201–208. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43352-2_16CrossRef

21.

Mansutti, A., Miculan, M., Peressotti, M.: Towards distributed bigraphical reactive systems. In: Echahed, R., Habel, A., Mosbah, M. (eds.) Proceedings of the GCM 2014, p. 45 (2014). workshop version

22.

Miculan, M., Peressotti, M.: Bigraphs reloaded: a presheaf presentation. Technical report UDMI/01/2013, Dept. of Mathematics and Computer Science, Univ. of Udine (2013). http://www.dimi.uniud.it/miculan/Papers/UDMI012013.pdf

23.

Miculan, M., Peressotti, M.: A CSP implementation of the bigraph embedding problem. CoRR abs/1412.1042 (2014)

24.

Miculan, M., Peressotti, M.: jLibBig: a library for bigraphical reactive systems, November 2015. https://github.com/bigraphs/jlibbig

25.

Milner, R.: The Space and Motion of Communicating Agents. Cambridge University Press, Cambridge (2009)CrossRefMATH

26.

Perrone, G., Debois, S., Hildebrandt, T.T.: Bigraphical refinement. In: Refine@FM. EPTCS, vol. 55, pp. 20–36 (2011)

27.

Perrone, G., Debois, S., Hildebrandt, T.T.: A model checker for bigraphs. In: Proceedings of the 27th Annual ACM Symposium on Applied Computing, pp. 1320–1325 (2012)

28.

Sahli, H., Ledoux, T., Rutten, É.: Modeling self-adaptive fog systems using bigraphs. In: Proceedings of the FOCLASA, Oslo, Norway, pp. 1–16, September 2019

29.

Sevegnani, M., Calder, M.: Bigraphs with sharing. Theoretical Computer Science 577, 43–73 (2015)MathSciNetCrossRefMATH

30.

Sevegnani, M., Unsworth, C., Calder, M.: A SAT based algorithm for the matching problem in bigraphs with sharing. University of Glasgow, Technical report (2010)

Title: Computing Embeddings of Directed Bigraphs
Authors: Alessio Chiapperini
Marino Miculan
Marco Peressotti
Publisher: Springer International Publishing
Book: Graph Transformation
Print ISBN: 978-3-030-51371-9

Electronic ISBN: 978-3-030-51372-6

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-51372-6_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner