Unfolding of Double-Pushout Graph Grammars is a Coreflection
Paolo Baldan, Andrea Corradini, Ugo Montanari · 1999
. 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. 1 Introduction In recent years, various concurrent semantics for graph rewriting systems have been proposed in the literature, some of ...