Antonin Delpeuch ; Jamie Vicary - Normalization for planar string diagrams and a quadratic equivalence algorithm

lmcs:6067 - Logical Methods in Computer Science, January 14, 2022, Volume 18, Issue 1 - https://doi.org/10.46298/lmcs-18(1:10)2022
Normalization for planar string diagrams and a quadratic equivalence algorithmArticle

Authors: Antonin Delpeuch ORCID; Jamie Vicary

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.

https://doi.org/10.46298/lmcs-18(1:10)2022
Source: arXiv.org:1804.07832
Volume: Volume 18, Issue 1
Published on: January 14, 2022
Accepted on: November 10, 2021
Submitted on: February 3, 2020
Keywords: Computer Science - Logic in Computer Science
Licence: Attribution 4.0 International (CC BY 4.0)

Classifications

Mathematics Subject Classification 20201
Sources:
  • [1] zbMATH Open.

Datasets

References
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-09) [Dataset]. Zenodo. 10.5281/ZENODO.17015893 1
Martens, M., Willighagen, E., & Evelo, C. (2023). Adverse Outcome Pathway Wiki RDF (Version 2023-04) [Dataset]. Zenodo. 10.5281/ZENODO.8297026 1
Martens, M., Willighagen, E., & Evelo, C. (2023). Adverse Outcome Pathway Wiki RDF (Version 2023-04) [Dataset]. Zenodo. 10.5281/ZENODO.8297025 1
Martens, M., Willighagen, E., & Evelo, C. (2026). Adverse Outcome Pathway Wiki RDF (Version 2026-03) [Dataset]. Zenodo. 10.5281/ZENODO.18821622 1
Martens, M., Willighagen, E., & Evelo, C. (2026). Adverse Outcome Pathway Wiki RDF (Version 2026-02) [Dataset]. Zenodo. 10.5281/ZENODO.18447235 1
Martens, M., Willighagen, E., & Evelo, C. (2026). Adverse Outcome Pathway Wiki RDF (Version 2026-01) [Dataset]. Zenodo. 10.5281/ZENODO.18113363 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-12) [Dataset]. Zenodo. 10.5281/ZENODO.17774419 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-11) [Dataset]. Zenodo. 10.5281/ZENODO.17499488 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-10) [Dataset]. Zenodo. 10.5281/ZENODO.17240212 1
Martens, M., Willighagen, E., & Evelo, C. (2023). Adverse Outcome Pathway Wiki RDF [Dataset]. Zenodo. 10.5281/ZENODO.*** 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-08) [Dataset]. Zenodo. 10.5281/ZENODO.16671771 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-07) [Dataset]. Zenodo. 10.5281/ZENODO.15779889 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-06) [Dataset]. Zenodo. 10.5281/ZENODO.15568399 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-05) [Dataset]. Zenodo. 10.5281/ZENODO.15314606 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-04) [Dataset]. Zenodo. 10.5281/ZENODO.15117729 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-03) [Dataset]. Zenodo. 10.5281/ZENODO.14995605 1
Martens, M., Willighagen, E., & Evelo, C. (2025). Adverse Outcome Pathway Wiki RDF (Version 2025-02) [Dataset]. Zenodo. 10.5281/ZENODO.14850921 1
Martens, M., Willighagen, E., & Evelo, C. (2023). Adverse Outcome Pathway Wiki RDF [Dataset]. Zenodo. 10.5281/ZENODO.10057880 1
  • 1 ScholeXplorer

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 3142 times.
This article's PDF has been downloaded 992 times.