Double-pushout graph transformation revisited 1
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.