SACS | An Algebra of Hierarchical Graphs and its Application to Structural Encoding

Published in Volume XX, 2010, pages 53-96

Authors: R. Bruni, F. Gadducci, and A. Lluch Lafuente

Abstract

We define an algebraic theory of hierarchical graphs, whose axioms characterise graph isomorphism: two terms are equated exactly when they represent the same graph. Our algebra can be understood as a high-level language for describing graphs with a node-sharing, embedding structure, and it is then well suited for defining graphical representations of software models where nesting and linking are key aspects. In particular, we propose the use of our graph formalism as a convenient way to describe configurations in process calculi equipped with inherently hierarchical features such as sessions, locations, transactions, membranes or ambients. The graph syntax can be seen as an intermediate representation language, that facilitates the encodings of algebraic specifications, since it provides primitives for nesting, name restriction and parallel composition. In addition, proving soundness and correctness of an encoding (i.e. proving that structurally equivalent processes are mapped to isomorphic graphs) becomes easier as it can be done by induction over the graph syntax.

Full Text (PDF)

References

[1] M. Boreale, R. Bruni, R. De Nicola, and M. Loreti. Sessions and pipelines for structured service programming. In G. Barthe and F. S. de Boer, editors, Proceedings of the 10th IFIP International Conference on Formal Methods for Open Object-based Distributed Systems (FMOODS’08), volume 5051 of Lecture Notes in Computer Science, pages 19-38. Springer Verlag, 2008.

[2] A. Boronat, R. Bruni, A. Lluch Lafuente, U. Montanari, and G. Paolillo. Exploiting the hierarchical structure of rule-based specifications for decision planning. In J. Hatcliff and E. Zucca, editors, Proceedings of the IFIP International Conference on Formal Techniques for Distributed Systems (FMOODS/FORTE’10), volume 6117 of Lecture Notes in Computer Science, pages 2-16. Springer Verlag, 2010.

[3] A. Boronat and J. Meseguer. An algebraic semantics for MOF. In J. Fiadeiro and P. Inverardi, editors, Proceedings of the 11th International Conference on Fundamental Aspects of Software Engineering (FASE’08), volume 4961 of Lecture Notes in Theoretical Computer Science, pages 377-391. Springer Verlag, 2008.

[4] R. Bruni, F. Gadducci, and A. Lluch Lafuente. An algebra of hierarchical graphs. In M. Hofmann and M. Wirsing, editors, Proceedings of the 5th International Symposium on Trustworthy Global Computing (TGC’10), Lecture Notes in Computer Science. Springer Verlag, 2010. To appear.

[5] R. Bruni, F. Gadducci, and A. Lluch Lafuente. A graph syntax for processes and services. In J. Su and C. Laneve, editors, Proceedings of the 6th International Workshop on Web Services and Formal Methods (WS-FM’09), volume 6194 of Lecture Notes in Computer Science, pages 46-60. Springer Verlag, 2010.

[6] R. Bruni, A. Lluch Lafuente, and U. Montanari. Hierarchical design rewriting with Maude. In G. Rosu, editor, Proceedings of the 7th International Workshop on Rewriting Logic and its Applications (WRLA’08), volume 238 (3) of Electronic Notes in Theoretical Computer Science, pages 45-62. Elsevier, 2009.

[7] R. Bruni, A. Lluch Lafuente, U. Montanari, and E. Tuosto. Style Based Architectural Reconfigurations. Bulletin of the European Association for Theoretical Computer Science (EATCS), 94:161-180, February 2008.

[8] R. Bruni, H. C. Melgratti, and U. Montanari. Theoretical foundations for compensations in flow composition languages. In J. Palsberg and M. Abadi, editors, Proceedings of the 32nd International Symposium on Principles of Programming Languages (POPL’05), pages 209-220. ACM, 2005.

[9] M. Bundgaard and V. Sassone. Typed polyadic pi-calculus in bigraphs. In A. Bossi and M. J. Maher, editors, Proceedings of the 8th International Symposium on Principles and Practice of Declarative Programming (PPDP’06), pages 1-12. ACM, 2006.

[10] G. Busatto, H.-J. Kreowski, and S. Kuske. Abstract hierarchical graph transformation. Mathematical Structures in Computer Science, 15(4):773-819, 2005.

[11] A. Corradini and F. Gadducci. An algebraic presentation of term graphs, via gs-monoidal categories. Applied Categorical Structures, 7(4):299-311, 1999.

[12] A. Corradini, U. Montanari, and F. Rossi. An abstract machine for concurrent modular systems: CHARM. Theoretical Computer Science, 122(1-2):165-200, 1994.

[13] A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R. Heckel, and M. L¨owe. Algebraic Approaches to Graph Transformation – Part I: Basic Concepts and Double Pushout Approach. In G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, pages 163-246. World Scientific, 1997.

[14] F. Drewes, B. Hoffmann, and D. Plump. Hierarchical graph transformation. Journal on Computer and System Sciences, 64(2):249-283, 2002.

[15] F. Drewes, H.-J. Kreowski, and A. Habel. Hyperedge replacement graph grammars. In G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, pages 95-162. World Scientific, 1997.

[16] H. Ehrig and B. Konig. Deriving bisimulation congruences in the DPO approach to graph rewriting with borrowed contexts. Mathematical Structures in Computer Science, 16(6):1133-1163, 2006.

[17] G. L. Ferrari, D. Hirsch, I. Lanese, U. Montanari, and E. Tuosto. Synchronised hyperedge replacement as a model for service oriented computing. In F. S. de Boer, M. M. Bonsangue, S. Graf, and W. P. de Roever, editors, Proceedings of the 4th International Symposium on Formal Methods for Components and Objects (FMCO’05), volume 4111 of Lecture Notes in Computer Science, pages 22-43. Springer Verlag, 2006.

[18] F. Gadducci. Term graph rewriting for the pi-calculus. In A. Ohori, editor, Proceedings of the 1st Asian Symposium on Programming Languages and Systems (APLAS’03), volume 2895 of Lecture Notes in Computer Science, pages 37-54. Springer Verlag, 2003.

[19] F. Gadducci and G. V. Monreale. A decentralized implementation of mobile ambients. In H. Ehrig, R. Heckel, G. Rozenberg, and G. Taentzer, editors, Proceedings of the 4th International Conference on Graph Transformation (ICGT’08), volume 5214 of Lecture Notes in Computer Science, pages 115-130. Springer, 2008.

[20] D. Grohmann and M. Miculan. Graph algebras for bigraphs. In J. K¨uster and E. Tuosto, editors, Proceedings of the 10th International Workshop on Graph Transformation and Visual Modeling Techniques (GT-VMT’10), Electronic Communications of the EASST, 2010. To appear.

[21] J. J. Leifer and R. Milner. Deriving bisimulation congruences for reactive systems. In C. Palamidessi, editor, Proceedings of the 11th International Conference on Concurrency Theory (CONCUR’00), volume 1877 of Lecture Notes in Computer Science, pages 243-258. Springer Verlag, 2000.

[22] R. Milner. Communicating and Mobile Systems: The π-calculus. Cambridge University Press, 1992.

[23] R. Milner. Pure bigraphs: Structure and dynamics. Information and Computation, 204(1):60-122, 2006.

[24] W. Palacz. Algebraic hierarchical graph transformation. Journal of Computer and System Sciences, 68(3):497-520, 2004.

[25] G. Paun. Membrane Computing. An Introduction. Springer, 2002.

[26] G. Paun and G. Rozenberg. A guide to membrane computing. Theoretical Computer Science, 287(1):73-100, 2002.

Bibtex

@article{sacscuza:bruni2010aaohgaiatse,
  title={An Algebra of Hierarchical Graphs and its Application to Structural Encoding},
  author={R. Bruni and F. Gadducci and A. Lluch Lafuente},
  journal={Scientific Annals of Computer Science},
  volume={20},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2010},
  pages={53--96},
  publisher={``A.I. Cuza'' University Press}
}