Nijmegen Quantum Logic Group

home people seminar

Confluence of Graph Rewriting with Interfaces

20 Dec 2017 [ proceedings ]

We show that confluence is decidable for an extension of DPO rewriting to graphs with interfaces.

For terminating double-pushout (DPO) graph rewriting systems confluence is, in general, undecidable. We show that confluence is decidable for an extension of DPO rewriting to graphs with interfaces. This variant is important due to it being closely related to rewriting of string diagrams. We show that our result extends, under mild conditions, to decidability of confluence for terminating rewriting systems of string diagrams in symmetric monoidal categories.