True Parallel Graph Transformations: an Algebraic Approach Based on Weak Spans
This work addresses a theoretical problem in graph transformation systems, which is incremental as it extends existing algebraic methods for parallel applications.
The paper tackles the problem of defining simultaneous graph transformations when direct transformations are not independent, using an algebraic approach with weak spans. It introduces parallel coherent transformations as a conservative extension of interleaving semantics and proposes a categorical construction for finitely attributed structures to build these transformations naturally.
We address the problem of defining graph transformations by the simultaneous application of direct transformations even when these cannot be applied independently of each other. An algebraic approach is adopted, with production rules of the form $L\xleftarrow{l}K \xleftarrow{i} I \xrightarrow{r} R$, called weak spans. A parallel coherent transformation is introduced and shown to be a conservative extension of the interleaving semantics of parallel independent direct transformations. A categorical construction of finitely attributed structures is proposed, in which parallel coherent transformations can be built in a natural way. These notions are introduced and illustrated on detailed examples.