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 dened 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 conrming the appropriateness of our unfolding construction, unify the various event structure semantics for the DPO approach to graph transformation.
Unfolding and Event Structure Semantics for Graph Grammars
CORRADINI, ANDREA;MONTANARI, UGO GIOVANNI ERASMO
1999-01-01
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 dened 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 conrming the appropriateness of our unfolding construction, unify the various event structure semantics for the DPO approach to graph transformation.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
