Rewriting modulo symmetric monoidal structure
Open Access
- 5 July 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 710-719
Abstract
String diagrams are a powerful and intuitive graphical syntax for terms of symmetric monoidal categories (SMCs). They find many applications in computer science and are becoming increasingly relevant in other fields such as physics and control theory. An important role in many such approaches is played by equational theories of diagrams, typically oriented and applied as rewrite rules. This paper lays a comprehensive foundation for this form of rewriting. We interpret diagrams combinatorially as typed hypergraphs and establish the precise correspondence between diagram rewriting modulo the laws of SMCs on the one hand and double pushout (DPO) rewriting of hypergraphs, subject to a soundness condition called convexity, on the other. This result rests on a more general characterisation theorem in which we show that typed hypergraph DPO rewriting amounts to diagram rewriting modulo the laws of SMCs with a chosen special Frobenius structure. We illustrate our approach with a proof of termination for the theory of non-commutative bimonoids.Keywords
All Related Versions
Funding Information
- ERC grant n o 320571 (FP7/2007-2013)
- ANR 12IS02001 PACE
- Labex MILYON/ANR- 10-LABX-0070
This publication has 29 references indexed in Scilit:
- The Category Theoretic Understanding of Universal Algebra: Lawvere Theories and MonadsElectronic Notes in Theoretical Computer Science, 2007
- Dagger Compact Closed Categories and Completely Positive MapsElectronic Notes in Theoretical Computer Science, 2007
- A basic algebra of stateless connectorsTheoretical Computer Science, 2006
- Adhesive and quasiadhesive categoriesRAIRO - Theoretical Informatics and Applications, 2005
- Traced monoidal categoriesMathematical Proceedings of the Cambridge Philosophical Society, 1996
- Higher-dimensional word problems with applications to equational logicTheoretical Computer Science, 1993
- The geometry of tensor calculus, IAdvances in Mathematics, 1991
- Matrices, relations, and group representationsJournal of Algebra, 1991
- Coherence for compact closed categoriesJournal of Pure and Applied Algebra, 1980
- Categorical algebraBulletin of the American Mathematical Society, 1965