Cospan DPO approach: an alternative for DPO graph transformations. (English) Zbl 1191.68361

Summary: The DPO approach for graph transformations is based on productions \(p=(L\leftarrow K\to R)\) and direct transformations defined by two pushouts, where, roughly speaking, in the first pushout all items in \(L\setminus K\) are deleted and in the second one all items \(R\setminus K\) are added, while those items in \(K\) are preserved. Intuitively, \(K\) is the intersection of \(L\) and \(R\) and, formally, \(p=(L\leftarrow K\to R)\) is a span of graph morphisms.
We consider productions \(\overline{p}= (L\to\overline{K}\leftarrow R)\) which are cospans of graph morphisms, and \(\overline{K}\) corresponds to the union of \(L\) and \(R\). As before, direct transformations are defined by double pushouts, but now the first pushout adds all items in \(\overline{K}\setminus L\) and the second one deletes \(\overline{K}\setminus R\). This basic idea can be extended to an alternative graph transformation approach, called cospan DPO approach. Key notions of the classical DPO approach can be reformulated in the cospan DPO approach and our main result shows in which way corresponding concepts and results are equivalent.


68Q42 Grammars and rewriting systems
68R10 Graph theory (including graph drawing) in computer science