Abstract
We propose an unfolding semantics for graph transformation systems in the double-pushout (DPO) approach. Mimicking Winskel’s construction for Petri nets, a graph grammar is unfolded into an acyclic branching structure, that is itself a (nondeterministic occurrence) graph grammar describing all the possible computations of the original grammar. The unfolding can be abstracted naturally to a prime algebraic domain and then to an event structure semantics. We show that such event structure coincides both with the one defined by Corradini et al. [3] via a comma category construction on the category of concatenable derivation traces, and with the one proposed by Schied [13], based on a deterministic variant of the DPO approach. This results, besides confirming the appropriateness of our unfolding construction, unify the various event structure semantics for the DPO approach to graph transformation.
Research partially supported by MURST project Tecniche Formali per Sistemi Software, by TMR Network GETGRATS and by Esprit WG APPLIGRAPH.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
P. Baldan, A. Corradini, and U. Montanari. An event structure semantics for P/T contextual nets: Asymmetric event structures. Proceedings of FoSSaCS’ 98, volume 1378, pages 63–80. Springer, 1998.
A. Corradini. Concurrent Graph and Term Graph Rewriting. Proceedings CONCUR’96, volume 1119 of LNCS, pages 438–464. Springer, 1996.
A. Corradini, H. Ehrig, M. Löwe, U. Montanari, and F. Rossi. An Event Structure Semantics for Graph Grammars with Parallel Productions. Proceedings of the 5th International Workshop on Graph Grammars and their Application to Computer Science, volume 1073 of LNCS. Springer, 1996.
A. Corradini, U. Montanari, and F. Rossi. Graph processes. Fundamenta Informaticae, 26:241–265, 1996.
A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R. Heckel, and M. Löwe. Algebraic Approaches to Graph Transformation I: Basic Concepts and Double Pushout Approach. In G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Transformation. Volume 1: Foundations. World Scientific, 1997.
H. Ehrig. Tutorial introduction to the algebraic approach of graph-grammars. Proceedings of the 3rd International Workshop on Graph-Grammars and Their Application to Computer Science, volume 291 of LNCS, pages 3–14. Springer, 1987.
R. Janicki and M. Koutny. Semantics of inhibitor nets. Information and Computation, 123:1–16, 1995.
H.-J. Kreowski. A comparison between Petri nets and graph grammars. Proceedings of the Workshop on Graphtheoretic Concepts in Computer Science, volume 100 of LNCS, pages 306–317. Springer, 1981.
J. Meseguer, U. Montanari, and V. Sassone. Process versus unfolding semantics for Place/Transition Petri nets. Theoret. Comput. Sci., 153(1-2):171–210, 1996.
U. Montanari and F. Rossi. Contextual nets. Acta Informatica, 32, 1995.
W. Reisig. Petri Nets: An Introduction. EACTS Monographs on Theoretical Computer Science. Springer, 1985.
L. Ribeiro. Parallel Composition and Unfolding Semantics of Graph Grammars. PhD thesis, Technische Universität Berlin, 1996.
G. Schied. On relating Rewriting Systems and Graph Grammars to Event Structures. Proceedings of the Dagstuhl Seminar 9301 on Graph Transformations in Computer Science, volume 776 of LNCS, pages 326–340. Springer, 1994.
W. Vogler. Efficiency of asynchronous systems and read arcs in Petri nets. Technical Report 352, Institüt für Mathematik, Augsburg University, 1996.
G. Winskel. Event Structures. In Petri Nets: Applications and Relationships to Other Models of Concurrency, volume 255 of LNCS, pages 325–392. Springer, 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baldan, P., Corradini, A., Montanari, U. (1999). Unfolding and Event Structure Semantics for Graph Grammars. In: Thomas, W. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 1999. Lecture Notes in Computer Science, vol 1578. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49019-1_6
Download citation
DOI: https://doi.org/10.1007/3-540-49019-1_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65719-4
Online ISBN: 978-3-540-49019-7
eBook Packages: Springer Book Archive