Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-09T14:52:58.266Z 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

Abstract

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.

Type
Research Article
Copyright
2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

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