Researchers Develop Systems Equating 2 Diagram Classes with Verified Term Rewriting Rules

Researchers are developing methods to formally verify the equivalence of diagrams, a crucial step in ensuring the correctness of complex systems such as electrical circuits. Julie Cailler, Noé Delorme and Simon Perdrix, all from Université de Lorraine, CNRS, INRIA, LORIA, Nancy, France, alongside Sophie Tourret working with colleagues at both Université de Lorraine, CNRS, INRIA, LORIA, Nancy, France and the Max Planck Institute for Informatics, Saarbrücken, Germany, present new term rewriting systems designed to equate terms representing diagrammatically equivalent structures. This work significantly advances automated reasoning about diagrammatic equivalence by providing terminating and confluent systems, formally proven correct using the Isabelle/HOL proof assistant, and thus offering a robust foundation for verifying circuit designs and other diagram-based models.

This work introduces a method for translating two-dimensional diagrams into one-dimensional terms, enabling the use of established term rewriting techniques to prove their equivalence. The core achievement lies in the creation of ‘normalizing’ rewriting systems, sets of rules that transform any diagram into a unique, simplified form, for two specific classes of diagrams. These systems have been rigorously verified using the Isabelle/HOL proof assistant, ensuring their correctness and reliability. The mathematical framework underpinning this approach utilizes monoidal categories, specifically PROs and PROPs, structures that define how diagrams are composed and manipulated. This advance addresses a growing need for algorithmic foundations to handle increasingly complex diagrammatic reasoning problems. Diagrammatic methods offer intuitive structural insights, particularly in quantum computing where visual representations of circuits are essential for optimisation and verification. By encoding diagrams as terms, researchers can leverage the power of automated tools to certify equivalence in a machine-checkable way. arbitrary state-and-effect-free PROs, where each diagram element has at least one input and one output, and the PRO of permutations, dealing with the rearrangement of connections. For both, they defined normal forms and associated rewriting systems, proving that these systems always terminate and produce a consistent result regardless of the order of operations. This guarantees that equivalent diagrams can be systematically transformed into identical normal forms, providing a definitive test for equivalence. The use of Isabelle/HOL is particularly significant, as it provides a formal guarantee of the correctness of the termination and confluence proofs. This research establishes foundational results for semi-automated verification techniques, paving the way for more sophisticated tools for quantum circuit verification and beyond. While previous work has explored diagrammatic equivalence through graph-based approaches or focused on specific calculi like ZX-calculus, this study remains firmly within a term-based setting, offering explicit normal forms and verified rewriting systems. A syntactic term-based representation underpins the work, encoding diagrams as terms with operations for sequential composition, represented by the operator #, and parallel composition, represented by the operator ⊗. This approach translates diagrammatic deformations into equations between terms, enabling the application of term rewriting techniques to prove diagram equivalences and leverage automated tools for termination and confluence proofs. The chosen framework facilitates rigorous, machine-checkable certification of diagrammatic equivalence, a crucial advantage for complex verification tasks. Initially, the research focuses on arbitrary state-and-effect-free PROs, which are structures allowing swapping of wires and defined by generators representing processes with at least one input and one output wire. A normalizing rewriting system is defined alongside a corresponding normal form, ensuring that any two diagrammatically equivalent terms can be rewritten into one another through a normalization procedure. This system is designed to reduce any given term to a unique, simplified form, thereby establishing equivalence in a systematic manner. Subsequently, the study extends to the PRO of permutations, a specific case lacking generators, building upon the previously established normal form. A canonizing rewriting system is then defined, aiming to produce a unique canonical form for every permutation. The termination and confluence of both rewriting systems, essential properties guaranteeing that the rewriting process always finishes and yields the same result regardless of the order of operations, are rigorously verified using the proof assistant Isabelle/HOL. This formal verification provides a high degree of confidence in the correctness and reliability of the developed methods. The research demonstrates the termination and confluence of normalizing term rewriting systems for two classes of diagrams, crucial for automated reasoning about diagrammatic equivalence. This system operates on terms generated from a set of generators, representing black box processes with inputs and outputs, composed sequentially and in parallel. The work establishes a normal form, a standardized representation to which equivalent diagrams can be reduced, facilitating machine-checkable verification of equivalence. Building upon this foundation, a canonizing rewriting system was developed for the PRO of permutations, achieving a unique canonical form for any permutation. This system guarantees both termination, that the rewriting process always halts, and confluence, that the process yields a single, unique result regardless of the rewriting path taken. The termination and confluence proofs for both systems were rigorously verified using the Isabelle/HOL proof assistant, providing a high degree of confidence in their correctness. By encoding diagrams as terms, the research provides a natural framework for certifying diagrammatic equivalence in a rigorous and machine-checkable way. This approach contrasts with methods relying on hypergraph isomorphism or purely graphical transformations, offering a distinct advantage through its explicit use of rewriting systems and normal forms. The development of these systems represents essential building blocks towards full-fledged quantum circuit verification, a key goal in the field of quantum computing. Researchers are developing formal systems to verify the equivalence of diagrams, a step towards trustworthy automated reasoning about complex systems. For years, the challenge has been bridging the gap between the intuitive visual nature of these diagrams and the rigorous demands of formal logic. While diagrams offer a compelling way to represent information, particularly in fields like electrical circuit design and quantum computing, their inherent ambiguity necessitates a precise mathematical foundation for verification. Previous attempts often relied on manual proof or incomplete automation, leaving room for error in all but the simplest cases. This work addresses this longstanding problem by establishing normalizing term rewriting systems for specific classes of diagrams. The significance lies not merely in demonstrating termination and confluence, essential properties for any automated reasoning tool, but in the methodology employed. Leveraging the Isabelle/HOL proof assistant provides an unusually high degree of confidence in the correctness of the system itself, a crucial factor when dealing with safety-critical applications. However, the current approach is limited to specific diagram types, and scaling these techniques to more general or complex diagrams remains a substantial hurdle. The field needs to move beyond bespoke solutions towards a unified framework capable of handling a wider range of diagrammatic languages. Future work might explore the application of machine learning techniques to assist in the discovery of coherence equations, or the development of more expressive logical foundations that can directly capture the semantics of diagrams. Ultimately, the goal is not just to verify existing diagrams, but to enable the design of new, demonstrably correct systems with greater efficiency and reliability.