Parallelism and concurrency of graph manipulations

Abstract

Graph manipulations are formalized as graph derivations within the framework of graph grammar theory. In this paper we generalize recently published ‘Church–Rosser’ and ‘Parallelism’ Theorems for graph derivations. Given a ‘sequential independent’ sequence of graph derivations G⇒H ⇒X the Parallelism Theorem states that there is also a sequential independent sequence via the same productions applied in reverse order, and a direct derivation G ⇒ X via the corresponding parallel production. In our ‘Concurrency Theorem’, the main result of this paper, the assumption of sequential independence is dropped. For each sequence of productions together with dependence relations (allowing later rules to depend on the effects of earlier productions), we construct a single ‘concurrent production’. The Concurrency Theorem states that each graph derivation sequence via the given sequence of productions, which respects all the dependence relations, can be performed in a single direct derivation via the ‘concurrent production’. Moreover this assignment becomes a bijective correspondence. This Concurrency Theorem is formulated and proved in the framework of the algebraic theory of graph grammars using new pushout and pullback lemmas for the 3- and 4- dimensional cubes. As corollaries we obtain the Parallelism Theorem and a theorem reducing the strong to the weak Church–Rosser-property of graph derivations. Applications of these results to various fields in computer science especially to data base systems, are sketched in the introduction. © 1980, All rights reserved.