# Normalization for planar string diagrams and a quadratic equivalence algorithm

arXiv: https://arxiv.org/abs/1804.07832 · HTML: https://mlsanity.com/paper/1804.07832/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2018.

## Built on by (most cited first, 2 of 2)

- [Functorial String Diagrams for Reverse-Mode Automatic Differentiation](https://mlsanity.com/paper/2107.13433/) (2021)
- [A Diagrammatic Calculus for a Functional Model of Natural Language Semantics](https://mlsanity.com/paper/2507.00782/) (2025)

## Abstract (arXiv)

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.