Normalization for planar string diagrams and a quadratic equivalence algorithm
arXiv:1804.07832 · doi:10.46298/lmcs-18(1:10)2022
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.
References in corpus (7)
- The ZX-calculus is complete for stabilizer quantum mechanics
- QIRAL: A High Level Language for Lattice QCD Code Generation
- Verifying the Steane code with Quantomatic
- Polygraphs of finite derivation type
- Towards 3-Dimensional Rewriting Theory
- Globular: an online proof assistant for higher-dimensional rewriting
- Testing Graph Isotopy on Surfaces