A Critical Pair Enumeration Algorithm for String Diagram Rewriting
Anna Matsui, Innocent Obi, Guillaume Sabbagh, Leo Torres, Diana Kessler, Juan F. Meleiro, Koko Muroya · 2026
Read A Critical Pair Enumeration Algorithm for String Diagram Rewriting by Anna Matsui, Innocent Obi, Guillaume Sabbagh, Leo Torres, Diana Kessler, Juan F. Meleiro, Koko Muroya (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-09433.txt.
Introduction
Anna Matsui and colleagues automate critical pair analysis for string diagram rewriting, a handy check for confluence in rewriting systems. Bonchi and coauthors had shown this analysis valid for string diagrams in symmetric monoidal categories. The new algorithm lists every critical pair of a left-connected system, working by concrete moves on hypergraphs. They prove it correct and complete for such categories lacking a Frobenius structure.
Catalog record
| CREATOR | Anna Matsui, Innocent Obi, Guillaume Sabbagh, Leo Torres, Diana Kessler, Juan F. Meleiro, Koko Muroya |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49769 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.09433
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Critical Pair Enumeration Algorithm for String Diagram Rewriting We are grateful to organisers of Adjoint School 2024 in which our collaboration started. Thanks: G.S. was funded by BNP Paribas CIB EMEA and the French Ministry of Research under CIFRE project No. 2021/1502. Affiliation: Johns Hopkins University, USA Thanks: D.K. was funded by an Advanced Research + Invention Agency (ARIA) Safeguarded AI: TA1.1 Theory grant. Affiliation: University of Washington, USA Thanks: K.M. was funded by JSPS, KAKENHI Project No. 22K17850, Japan. Affiliation: University of Technology of Compiègne, France Anna Matsui, Innocent Obi, Guillaume Sabbagh, Leo Torres, Diana Kessler, Juan F. Meleiro, Koko Muroya Abstract Critical pair analysis provides a convenient and computable criterion of confluence, which is a fundamental property in rewriting theory, for a wide variety of rewriting systems. Bonchi et al. showed validity of critical pair analysis for rewriting on string diagrams in symmetric monoidal categories. This work aims at automation of critical pair analysis for string diagram rewriting, and develops an algorithm that implements the core part of critical pair analysis. The algorithm enumerates all critical pairs of a given left-connected string diagram rewriting system, and it can be realised by concrete manipulation of hypergraphs. We prove correctness and exhaustiveness of the algorithm, for string diagrams in symmetric monoidal categories without a Frobenius structure. 1 Introduction 1.1 Rewriting Theory and Critical Pair Analysis Mathematical reasoning often involves derivation of a (complex) equation from known (typically simpler) equations, which is sometimes called equational reasoning . Equations can be between various mathematical objects, e.g. terms, programs, graphs, processes, and objects/morphisms in a category. Rewriting theory has been established (see e.g. [ 3 , 16 ] ), with equational reasoning as one application. The starting point is to turn known equations a=a^{\prime} into directed 1 1 1 The direction is typically chosen so that a^{\prime} is “simpler” than a . rewrite rules a\multimap a^{\prime} . Each step b\to b^{\prime} of rewrite modifies a part of b by applying one rewrite rule. Derivation of an equation c\overset{?}{=}c^{\prime} then boils down to finding some d with two chains c\rightarrow\cdots\rightarrow d and c^{\prime}\rightarrow\cdots\rightarrow d of rewrites. These chains altogether imply a chain of equations c=\cdots=d=\cdots=c^{\prime} , which concludes the desired equation c\overset{?}{=}c^{\prime} . Confluence is a fundamental property in rewriting theory, intuitively meaning that ordering of rewrites does not matter. Rewrites \rightarrow are said to be confluent if any two diverging chains b\leftarrow\cdots\leftarrow a\rightarrow\cdots\rightarrow b^{\prime} of rewrites are joinable , that is, there exists c with converging chains b\rightarrow\cdots\rightarrow c\leftarrow\cdots\leftarrow b^{\prime} . Local confluence is a variant of confluence in which the two diverging chains are in fact given by two single rewrites, i.e. b\leftarrow a\rightarrow b^{\prime} . For some pairs of two diverging rewrites b\leftarrow a\rightarrow b^{\prime} , joinability is obvious. An example is the so-called parallel case, namely when the two rewrites change different, independent, parts of a . Consequently, checking local confluence boils down to analysing joinability of non-parallel pairs. Critical pair analysis is a well-established technique for automatically checking local confluence, providing a convenient and computable criterion. It reduces local confluence to joinability of critical pairs that are finitely many representatives of non-parallel pairs. Critical pairs can be enumerated from a given set of rewrite rules a\multimap a^{\prime} . This enumeration plays a central role in automating local-confluence check. 1.2 String Diagram Rewriting String diagrams [ 13 , 17 ] provide a graphical syntax of category theory. They are useful in equational reasoning on morphisms of a category, because they trivialise certain equations as graph isomorphisms. Rewriting theory for string diagrams has been developed by Bonchi et al. [ 4 , 5 , 6 ] , targeting at string diagrams for symmetric monoidal categories (with and without a Frobenius structure). String diagrams are combinatorially represented using hypergraphs, and rewrites on string diagrams are categorically modelled using double pushout rewriting (DPO rewriting in short) [ 8 ] . A key concept in string diagram rewriting theory is that of interface . An interface of a hypergraph specifies how other hypergraphs can be connected to the hypergraph. Bonchi et al. showed validity of critical pair analysis for string diagram rewriting [ 6 ] . They defined critical pairs for an adaptation of DPO rewriting (dubbed convex 2 2 2 Convexity is for dealing with the absence of a Frobenius structure. DPOI rewriting ) that takes interface into account, and proved that joinability of critical pairs implies local confluence. Their development focuses on a theoretical side, and automation, which is an important aspect of critical pair analysis, has not been investigated. 1.3 Contributions We aim at automation of critical pair analysis for string diagram rewriting, and develop an algorithm that implements the core part of the automation. The algorithm enumerates all critical pairs for a given set of DPOI rewrite rules. We focus on the so-called left-connected DPOI rewrite rules [ 5 , 6 ] . Left-connectivity allows us to reduce enumeration of critical pairs to enumeration of certain cospans in the category of hypergraphs. While it is an arguably powerful restriction, it still accommodates various concrete string diagram rewriting systems from the literature [ 10 , 11 , 14 ] . Each critical pair is associated with two DPOI rewrite rules, which are given by spans L_{1}\leftarrow K_{1}\rightarrow R_{1} and L_{2}\leftarrow K_{2}\rightarrow R_{2} in the category of hypergraphs. Thanks to left-connectivity, the critical pair is uniquely determined by a certain cospan of the form L_{1}+L_{2}\twoheadrightarrow S\leftarrow J . Its left leg is, in particular, an epimorphism given by the coupling of monomorphisms. Our key idea is that the cospan, in particular the hypergraph S , can be generated by suitably gluing hyperedges and nodes of L_{1}+L_{2} (i.e. the hypergraph that puts L_{1} and L_{2} in parallel). We observe that the gluing process can be realised in two steps: (1) repeatedly merge a hyperedge from L_{1} with a hyperedge from L_{2} , and (2) repeatedly merge a node from L_{1} with a node from L_{2} without merging any hyperedges. Our contributions can be summarised as follows. • We develop an algorithm (Algo. 3 ) that enumerates all critical pairs of a given set of left-connected DPOI rewrite rules by implementing the two-fold gluing process. • We prove that the algorithm generates all critical pairs and nothing else (correctness and exhaustiveness; Thm. 3.9 ). • We provide a proof-of-concept Haskell implementation 3 3 3 available online at https://github.com/GuiSab/hypergraphrewriting . • We present an optimised algorithm (Algo. 4 ) that enumerates less but sufficient critical pairs to decide local confluence by only performing the first step of the two-fold gluing process. Organisation. Sec. 2 recalls relevant concepts (e.g. hypergraph, interface, DPOI rewriting, critical pair) from string diagram rewriting theory [ 4 , 5 , 6 ] . Sec. 3 presents our main contribution, the critical pair enumeration algorithm with a proof of its correctness and exhaustiveness. Sec. 4 provides the optimised algorithm, and Sec. 5 concludes the paper. Examples and some proofs can be found in the Appendix. Related work. For term rewriting, rewrite rules typically use variables as placeholders to succinctly represent a family of rewrite rules, e.g. x+y\multimap y+x . To deal with variables, enumeration of critical pairs employs a technique called