Mathematical Structures in Computer Science

Double-pushout graph transformation revisited 1

a1 Universität Oldenburg, Fachbereich Informatik, 26111 Oldenburg, Germany
a2 28 Chichester Road, Seaford, East Sussex BN25 2DL, United Kingdom
a3 The University of York, Department of Computer Science, York YO10 5DD, United Kingdom


In this paper we investigate and compare four variants of the double-pushout approach to graph transformation. As well as the traditional approach with arbitrary matching and injective right-hand morphisms, we consider three variations by employing injective matching and/or arbitrary right-hand morphisms in rules. We show that injective matching provides additional expressiveness in two respects: for generating graph languages by grammars without non-terminals and for computing graph functions by convergent graph transformation systems. Then we clarify for each of the three variations whether the well-known commutativity, parallelism and concurrency theorems are still valid and – where this is not the case – give modified results. In particular, for the most general approach with injective matching and arbitrary right-hand morphisms, we establish sequential and parallel commutativity by appropriately strengthening sequential and parallel independence.

(Received August 20 1999)
(Revised August 31 2000)


1 This research was partly supported by the ESPRIT Working Group APPLIGRAPH. This paper is an extension of Habel et al. (2000).

2 J. Müller's contribution was also supported by the EC TMR Network GETGRATS, through the Universities of Antwerp and Pisa.

3 D. Plump's contribution was done while he was with Universität Bremen; part of his work was done during a visit at the Vrije Universiteit in Amsterdam.