Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T04:17:42.178Z Has data issue: false hasContentIssue false

Double-pushout graph transformation revisited

Published online by Cambridge University Press:  25 September 2001

ANNEGRET HABEL
Affiliation:
Universität Oldenburg, Fachbereich Informatik, 26111 Oldenburg, Germany
JÜRGEN MÜLLER
Affiliation:
28 Chichester Road, Seaford, East Sussex BN25 2DL, United Kingdom
DETLEF PLUMP
Affiliation:
The University of York, Department of Computer Science, York YO10 5DD, United Kingdom
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
2001 Cambridge University Press