Talk "Confluence of Graph Rewriting with Interfaces"

by Filippo Bonchi

Mon, 09 January 2017 at 03:00 pm in Binz (Rügen), Germany

Joint work with: Aleks kissinger, Fabio Gadducci, Pawel Sobocincki, Fabio Zanasi

Abstract: For terminating double-pushout (DPO) graph rewriting systems, confluence has been proved to be in general undecidable. We show that confluence is decidable for an extension of DPO rewriting to graphs with interfaces. This variant has become increasingly important in recent years, due to it being closely related to rewriting of string diagrams. We exploit this connection and show that our result extends, under mild conditions, to decidability of confluence for terminating rewriting systems of string diagrams in symmetric monoidal categories.