Normalization for planar string diagrams and a quadratic equivalence algorithm

Antonin Delpeuch, Jamie Vicary

Introduction

String diagrams serve as a powerful graphical syntax for monoidal categories, finding applications across diverse fields such as quantum computing, natural language processing, and logic. In these diagrams, wires represent objects (data types) and vertices represent morphisms (processes). A fundamental problem in the computational use of these diagrams is determining equivalence: when do two distinct graphical representations correspond to the same underlying mathematical morphism?

Geometrically, two diagrams are equivalent if one can be deformed into the other without breaking wires or reversing the orientation of vertices—a property known as recumbent isotopy. While intuitive for humans, this topological equivalence is computationally challenging. This paper provides the first general complexity results for deciding the equivalence of planar string diagrams, introducing efficient algorithms for both connected and general cases.

The Geometry of String Diagrams

A long-standing question in category theory, often referred to as Selinger’s conjecture, asks whether recumbent isotopy is equivalent to general isotopy in the plane. The authors settle this conjecture by proving that if two diagrams are topologically equivalent, they can be transformed into one another using only "exchange moves" that preserve the downward flow of wires. This theoretical breakthrough simplifies the problem from continuous topology to discrete rewriting.

A typical planar string diagram with vertices and wires.

Methodology: Rewriting and Normalization

The authors approach the equivalence problem through the lens of rewriting theory. The process involves several key steps:

  1. Combinatorial Encoding: Continuous diagrams are discretized into horizontal layers. Each layer contains exactly one vertex, effectively turning a 2D diagram into a 1D sequence of slices.
  2. Exchange Moves: The core mechanic is the "exchange move," which allows swapping the vertical heights of two adjacent vertices provided they do not share any wires.
  3. Normal Forms: By consistently applying exchange moves in a specific direction (e.g., moving vertices "to the right"), the authors show that diagrams can be reduced to a unique normal form.
Illustration of the normalization process where exchange moves are applied to reach a canonical representation.

For connected diagrams, this rewriting process is proven to be strongly normalizing and confluent, meaning it always terminates in the same unique result regardless of the order of moves.

Handling Disconnected Diagrams

General diagrams may contain disconnected components nested within the "faces" or "holes" created by other components. To manage this complexity, the authors introduce structural trees. These trees capture the nesting relationships between components, allowing the algorithm to recursively handle complex topologies that lack global connectivity.

Key Algorithmic Results

The paper establishes significant complexity bounds for the equivalence problem:

  • Linear-Time Equivalence: For "boundary-connected" diagrams—where every component is linked to the input or output wires—equivalence can be decided in $O(v + e)$ time, where $v$ is the number of vertices and $e$ is the number of edges. This is achieved by reducing the problem to planar map isomorphism.
  • Quadratic-Time General Case: For arbitrary planar diagrams, the algorithm runs in $O(ve)$ time.
  • Termination Bounds: The authors proved that the normalization process for a diagram with $n$ vertices terminates in at most $O(n^3)$ exchange moves.

Conclusion and Future Directions

This work provides a solid algorithmic foundation for the automated manipulation of string diagrams. By proving Selinger’s conjecture and establishing efficient complexity bounds, it paves the way for more robust tools in quantum programming and formal verification.

Future research will focus on extending these results to braided or symmetric monoidal categories, where wires are permitted to cross. Such extensions are critical for practical applications like the ZX-calculus. Additionally, while the current algorithms are theoretically optimal, practical implementations in proof assistants like homotopy.io may benefit from further optimizations, such as the use of hashing for structural tree comparisons.

Summary updated

Abstract

In the graphical calculus of planar string diagrams, equality is generated by exchange moves, which swap the heights of adjacent vertices. We show that left- and right-handed exchanges each give strongly normalizing rewrite strategies for connected string diagrams. We use this result to give a linear-time solution to the equivalence problem in the connected case, and a quadratic solution in the general case. We also give a stronger proof of the Joyal-Street coherence theorem, settling Selinger's conjecture on recumbent isotopy.
BibTeX
@article{delpeuch2022normalization,
  author = {Antonin Delpeuch and Jamie Vicary},
  title = {{Normalization for planar string diagrams and a quadratic equivalence algorithm}},
  journal = {Log. Methods Comput. Sci.},
  year = {2022},
  doi = {10.46298/lmcs-18(1:10)2022},
}

Loading related content...

Figure