Concatenable Graph Processes:
Relating Processes and Derivation Traces

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

Abstract:

Several formal concurrent semantics have been proposed for graph rewriting, a powerful formalism for the specification of concurrent and distributed systems, which generalizes P/T Petri nets. In this paper we relate two such semantics recently proposed for the algebraic double-pushout approach to graph rewriting, namely the derivation trace and the graph process semantics. The notion of concatenable graph process is introduced and then the category of concatenable derivation traces is shown to be isomorphic to the category of concatenable graph processes. As an outcome we obtain a more intuitive characterization of the events and of the configurations of the event structure associated to a graph grammar.