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.
Bonchi F., Gadducci F., Kissinger A., Sobocinski P., Zanasi F. (2017). Confluence of graph rewriting with interfaces. HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY : Springer Verlag [10.1007/978-3-662-54434-1_6].
Confluence of graph rewriting with interfaces
Zanasi F.
2017
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
