String diagram rewrite theory III: Confluence with and without Frobenius

Journal article

In this paper we address the problem of proving confluence for string diagram rewriting, which was previously shown to be characterised combinatorically as double-pushout rewriting with interfaces (DPOI) on (labelled) hypergraphs. For standard DPO rewriting without interfaces, confluence for terminating rewrite systems is, in general, undecidable. Nevertheless, we show here that confluence for DPOI, and hence string diagram rewriting, is decidable. We apply this result to give effective procedures for deciding local confluence of symmetric monoidal theories with and without Frobenius structure by critical pair analysis. For the latter, we introduce the new notion of path joinability for critical pairs, which enables finitely many joins of a critical pair to be lifted to an arbitrary context in spite of the strong non-local constraints placed on rewriting in a generic symmetric monoidal theory

Authors: Bonchi, F; Gadducci, F; Kissinger, A; Sobociński, P; Zanasi, F

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Mathematical Structures in Computer Science
• Volume: 32
• Issue: 7
• Pages: 829-869
• Publication date: 2022-06-13
• DOI: 10.1017/s0960129522000123
• EISSN: 1469-8072
• ISSN: 0960-1295
• Language: English
• Keywords: String (physics); Mathematics; Computer science; Undecidable problem; Normalization property; Decidability; Discrete mathematics; Algebra over a field; Confluence; Pure mathematics; Programming language; Diagram; Rewriting