Amalgamation of Graph Transformations with Applications to Synchronization
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.