CONCURRENT SEMANTICS OF ALGEBRAIC GRAPH TRANSFORMATIONS

Paolo Baldan⁽¹⁾, Andrea Corradini⁽¹⁾, HartmutEhrig⁽²⁾, Michael Löwe⁽²⁾, Ugo Montanari⁽¹⁾, Francesca Rossi⁽¹⁾

(1)   University of Pisa, Computer Science Department,
        Corso Italia 40, 56125 Pisa, Italy
        {baldan,andrea,ugo,rossi}@di.unipi.it

(2)  Techincal University of Berlin, Computer Science Department,
       Franklinstrasse 28/29, 10587 Berlin, Germany.
       {ehrig,loewe}@cs.tu-berlin.de

 

Graph transformation systems are widely recognized as a powerful formalism for the specification of concurrent and distributed systems. Therefore, the need emerges naturally of developing formal concurrent semantics for graph transformation systems allowing for a suitable description and analysis of their computational properties. The aim of this chapter is to review and compare various concurrent semantics for the double pushout (DPO) algebraic approach to graph transformation, using different mathematical structures and describing computations at different levels of abstraction. We first present a trace semantics, based on the classical shift equivalence on graph derivations. Next we introduce graph processes, which lift to the graph transformation framework the notion of non-sequential process for Petri nets. Trace and process semantics are shown to be equivalent, in the sense that given a graph transformation system, the corresponding category of derivation traces and that of (concatenable) processes turns out to be isomorphic. Finally, a more abstract description of graph transformation systems computations is given by defining a semantics based on Winskel's event structures.