Double-pushout graph transformation revisited (Q2762625)

The double-pushout approach to graph transformation was introduced in 1973 in a paper by Ehrig, Pfender and Schneider. Since then the approach has been studied extensively and has also been applied to several areas of computer science. In the mentioned paper, the left-hand sides of transformation rules are matched by injective graph morphisms, but the vast majority of later papers on the double-pushout approach consider arbitrary, possibly non-injective matching morphisms. NEWLINENEWLINENEWLINEThe present paper argues that despite this tradition, injective matching makes the approach more expressive. 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. NEWLINENEWLINENEWLINETwo variants of the double-pushout approach are considered in which matching morphisms are required to be injective. These approaches are denoted by \(DPO^{i/i}\) and \(DPO^{a/i}\), where the first component of the exponent indicates whether right-band morphisms in rules are injective or arbitrary, and where the second component refers to the requirement for matching morphisms. Besides the traditional approach \(DPO^{i/a}\), also \(DPO^{a/a}\) is considered. Obviously, \(DPO^{a/a}\) and \(DPO^{a/i}\) contain \(DPO^{i/a}\) and \(DPO^{i/i}\), respectively, as the rules of the latter approaches are included in the former approaches. Moreover, a quotient construction for rules permits to show that \(DPO^{i/i}\) and \(DPO^{a/i}\) can simulate \(DPO^{i/a}\) and \(DPO^{a/a}\), respectively, in a precise and strong way. NEWLINENEWLINENEWLINEFinally, the paper addresses the problem whether the theory developed for \(DPO^{i/a}\) carries over to the stronger approaches. The question is answered for the classical commutativity, parallelism and concurrency theorems, by either establishing their validity or by giving counterexamples and providing modified results.