Unfolding of Double-Pushout Graph Grammars
is a Coreflection

Paolo Baldan - Andrea Corradini - Ugo Montanari    

Abstract:

In a recent paper, mimicking Winskel's construction for Petri nets, a concurrent semantics for (double-pushout) DPO graph grammars has been provided by showing that each graph grammar can be unfolded into an acyclic branching structure, that is itself a (nondeterministic occurrence) graph grammar describing all the possible computations of the original grammar.

This paper faces the problem of providing a closer correspondence with Winskel's result by showing that the unfolding construction can be described as a coreflection between the category of graph grammars and the category of occurrence graph grammars. The result is shown to hold for a suitable subclass of graph grammars, called semi-weighted graph grammars. Unfortunately the coreflection does not extend to the whole category of graph grammars: some ideas for solving the problem are suggested.