On Hierarchical Graphs : Reconciling Bigraphs, Gs-monoidal Theories and Gs-graphs

• Autorzy: Bruni R. , Montanari U. , Plotkin G. , Terreni D.

Identyfikatory

DOI

10.3233/FI-2014-1103

• Języki publikacji: EN

Abstrakty

EN

Compositional graph models for global computing systems must account for two relevant dimensions, namely structural containment and communication linking. In Milner’s bigraphs the two dimensions are made explicit and represented as two loosely coupled structures: the place graph and the link graph. Here, bigraphs are compared with an earlier model, gs-graphs, originally conceived for modelling the syntactical structure of agents with α-convertible declarations. We show that gs-graphs are quite convenient also for the new purpose, since the two above mentioned dimensions can be recovered by considering only a specific class of hyper-signatures. With respect to bigraphs, gs-graphs can be proved essentially equivalent, with minor differences at the interface level.We argue that gs-graphs offer a simpler and more standard algebraic structure, based on monoidal categories, for representing both states and transitions.Moreover, they can be equipped with a simple type system to check the well-formedness of legal gs-graphs that are shown to characterise binding bigraphs. Another advantage concerns a textual form in terms of sets of assignments, which can make implementation easier in rewriting frameworks like Maude.

Słowa kluczowe

EN

gs-monoidal theories; gs-graphs; pure bigraphs; binding bigraphs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 3/4
• Strony: 287--317
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Bruni R.

• Computer Science Department, University of Pisa, Italy

autor

Montanari U.

• Computer Science Department, University of Pisa, Italy

autor

Plotkin G.

• LFCS, School of Informatics, University of Edinburgh, UK

autor

Terreni D.

• Computer Science Department, University of Pisa, Italy

Bibliografia

• [1] R. Bruni, A. Corradini, F. Gadducci, A. Lluch-Lafuente, and U. Montanari. On gs-monoidal theories for graphs with nesting. In Graph Transformations and Model-Driven Engineering, volume 5765 of LNCS, pages 59–86. Springer, 2010.
• [2] R. Bruni, F. Gadducci, and U. Montanari. Normal forms for algebras of connection. Theor. Comput. Sci., 286(2):247–292, 2002.
• [3] R. Bruni, U. Montanari, and F. Rossi. An interactive semantics of logic programming. TPLP, 1(6):647–690, 2001.
• [4] L. Cardelli and A. D. Gordon. Mobile ambients. Theor. Comput. Sci., 240(1):177–213, 2000.
• [5] A. Corradini and F. Gadducci. A 2-categorical presentation of term graph rewriting. In CTCS’97, volume 1290 of LNCS, pages 87–105. Springer, 1997.
• [6] A. Corradini and F. Gadducci. An algebraic presentation of term graphs, via gs-monoidal categories. Applied Categorical Structures, 7(4):299–331, 1999.
• [7] A. Corradini and F. Gadducci. On term graphs as an adhesive category. Electr. Notes Theor. Comput. Sci., 127(5):43–56, 2005.
• [8] V.-E. Căzănescu and G. Stefănescu. A general result on abstract flowchart schemes with applications to the study of accessibility, reduction and minimization. Theoretical Comput. Sci., 99(1):1–63, 1992.
• [9] T. C. Damgaard and L. Birkedal. Axiomatizing binding bigraphs. Nord. J. Comput., 13(1-2):58–77, 2006.
• [10] G. L. Ferrari and U.Montanari. Tile formats for located andmobile systems. Inf. Comput., 156(1-2):173–235, 2000.
• [11] M. P. Fiore and M. D. Campos. The algebra of directed acyclic graphs. In B. Coecke, L. Ong, and P. Panangaden, editors, Computation, Logic, Games, and Quantum Foundations, volume 7860 of LNCS, pages 37–51. Springer, 2013.
• [12] R. H. G. Garner, T. Hirschowitz, and A. Pardon. Variable binding, symmetric monoidal closed theories, and bigraphs. In CONCUR’09, volume 5710 of LNCS, pages 321–337. Springer, 2009.
• [13] P. Hackney and M. Robertson. On the category of props, 2012. arXiv:1207.2773.
• [14] O. Jensen and R. Milner. Bigraphs and mobile processes (revised). Technical Report UCAM-CL-TR-580, University of Cambridge, 2004.
• [15] O. H. Jensen and R. Milner. Bigraphs and transitions. In POPL, pages 38–49, 2003.
• [16] M. Johnson and D. Yau. On homotopy invariance for algebras over colored PROPs. Journal of Homotopy and Related Structures, 4:275–315, 2009.
• [17] S. Lack. Composing PROPS. Theory and Applications of Categories, 13(9):147–163, 2004.
• [18] S. MacLane. Categorical algebra. Bulletin of the American Mathematical Society, 71(1):40–106, 1965.
• [19] S. MacLane. Categories for the Working Mathematician. Graduate Texts in Mathematics 5. Springer, 2nd edition, 1998.
• [20] J. Meseguer. Membership algebra as a logical framework for equational specification. In WADT’97, volume 1376 of LNCS, pages 18–61. Springer, 1997.
• [21] R. Milner. Bigraphical reactive systems. In CONCUR’01, volume 2154 of LNCS, pages 16–35. Springer, 2001.
• [22] R. Milner. Bigraphs whose names have multiple locality. Technical Report UCAM-CL-TR-603, University of Cambridge, 2004.
• [23] R. Milner. Bigraphs and their algebra. Electr. Notes Theor. Comput. Sci., 209:5–19, 2008.
• [24] R. Milner. The Space and Motion of Communicating Agents. Cambridge University Press, 2009.
• [25] V. Sassone and P. Sobocinski. Locating reaction with 2-categories. Theor. Comput. Sci., 333(1-2):297–327, 2005.
• [26] P. Selinger. A survey of graphical languages for monoidal categories. In B. Coecke, editor, New Structures for Physics, volume 813 of Lecture Notes in Physics, pages 289–355. Springer, 2011.