Unfolding and Event Structure Semantics
for Graph Grammars

Paolo Baldan - Andrea Corradini - Ugo Montanari Dipartimento di Informatica University of Pisa Corso Italia, 40, 56125 Pisa, Italy

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. [1] via a comma category construction on the category of concatenable derivation traces, and with the one proposed by Schied [2], 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.

1. A. Corradini, H. Ehrig, M. Lowe, 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.
2. G. Schied. On relating Rewriting Systems and Graph Grammars to Event Sructures. Proceedings of the Dagstuhl Seminar 9301 on Graph Transformations in Computer Science, volume 776 of LNCS, pages 326--340. Springer, 1994.