Normal forms for planar connected string diagrams

Antonin Delpeuch, Jamie Vicary

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.

Introduction

String diagrams serve as a powerful geometric notation for describing processes in fields ranging from quantum computing to natural language processing. In these diagrams, wires represent data types and vertices represent processes. A fundamental challenge in the graphical calculus of monoidal categories is the "word problem": determining if two diagrams are equivalent under isotopy—that is, if one can be deformed into the other without breaking or crossing wires.

Historically, the complexity of deciding diagram equivalence lacked a general analysis. Furthermore, the standard definition of equivalence relied on "recumbent isotopy," where wires remain essentially "upright" during deformation. This paper provides the first general complexity results for planar string diagrams and settles Selinger’s conjecture, proving that the constraint of recumbency is redundant.

Methodology and Key Insights

The authors approach the equivalence problem by bridging the gap between geometric "wiggling" and formal algebraic exchange laws. The methodology relies on several key pillars:

  1. Combinatorial Encoding: Diagrams are represented as sequences of "slices," each containing exactly one vertex. This converts geometric objects into discrete data structures.
  2. Exchange Moves and Normalization: The authors define "left" and "right" exchange moves—rules for swapping the vertical heights of adjacent, non-connected vertices. They prove that applying these moves in a specific direction (e.g., "right reduction") is strongly normalizing and confluent for connected diagrams. This ensures a unique "Right Normal Form" exists.
  3. Structural Classification: A critical insight is the distinction between connected and disconnected diagrams. Connected diagrams possess a rigid structure that allows for more efficient processing. For disconnected diagrams, the authors develop a "structural tree" to capture the nesting of components within the faces of others.
Classification of string diagrams: (A) Disconnected, (B) Connected, and (C) Boundary-connected.

Results

The paper establishes significant complexity bounds and theoretical proofs:

  • Connected Diagrams: Equivalence can be decided in linear time ($O(v + e)$), 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.
  • General Diagrams: For disconnected diagrams, equivalence is decidable in quadratic time ($O(ve)$).
  • Termination: Any sequence of right exchange moves on a diagram with $n$ vertices terminates in at most $O(n^3)$ steps.
  • Coherence and Selinger’s Conjecture: The authors prove that general isotopy is equivalent to recumbent isotopy. This simplifies the foundations of string diagram theory and provides a stronger proof of the Joyal-Street coherence theorem.

Discussion and Future Work

While this work provides a robust framework for planar string diagrams in strict monoidal categories, it does not yet extend to braided or symmetric monoidal categories where wires can cross. The results assume a RAM model with constant-time arithmetic; for exceptionally large diagrams, the cost of handling large integers in structural tree encodings may become relevant.

Future applications include implementing these algorithms as "tactics" in automated proof assistants like homotopy.io or Quantomatic, enabling automated simplification and comparison of complex graphical proofs.

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{delpeuch2022normal,
  author = {Antonin Delpeuch and Jamie Vicary},
  title = {{Normal forms for planar connected string diagrams}},
  journal = {Log. Methods Comput. Sci.},
  year = {2022},
  doi = {10.46298/lmcs-18(1:10)2022},
}

Loading related content...

Figure