Amalgamation of graph transformations: A synchronization mechanism

摘要

In the present paper we generalize the well-known Parallelism Theorem for graph derivations to the Amalgamation Theorem. In this theorem the assumption of “parallel independence” is dropped. For each pair of productions together with a relational production (allowing productions to be associated with each other) we construct a single “amalgamated” production. The Amalgamation Theorem states that graph derivations which respect the given associations can be amalgamated to a single derivation via the “amalgamated” production. The amalgamation of graph transformations can be considered as a synchronization mechanism. The amalgamation concept is applied to synchronization of graph manipulations in a simplified railway control system as well as to a graph grammar formalism for distributed systems (GDS).