Parallel and distributed derivations in the single-pushout approach (Q685462)

The paper studies the relationship among various kinds of parallel and distributed direct derivations in the framework of the algebraic, single- pushout approach to graph rewriting, introduced in the companion paper by the second author [ibid., 181-224 (1993; Zbl 0787.18002)]. Definitions and results are stated in purely categorical terms, thus they apply not only to various kinds of graphs, but also to other, more general structures. A parallel direct derivation is the result of applying a parallel rule (i.e., the disjoint union of two rules) to an object. The splitting of an object is a pushout showing how the object is obtained as the glueing of two other objects along a common interface. A distributed direct derivation is obtained by taking the splitting of an object, by applying two rules to the sub-components, and then by glueing the two results along the starting interface. Depending on whether total or partial splitting is considered, various kinds of distributed derivations can be obtained. The main results of the paper state conditions under which parallel and distributed derivations are equivalent, and provide a strict hierarchy of various kinds of derivations. Finally, dynamic distributed derivations (i.e., such that the interface object can be transformed as well, via the application of a third production) are shown to be equivalent to direct amalgamated derivations, i.e., derivations via an amalgamated rule obtained by overlapping two rules on a common subrule. The paper is sound and well-written, but it requires a good background in the theory of algebraic approach to graph grammars (including the paper mentioned above). Its results compare favourably with related results in the double-pushout approach, because the presence of partial morphisms makes the formal framework richer. The technical proofs show the usefulness of the pure categorical setting, because most of them reduce to careful diagram chasing.