Milosavljević, A;
Piedeleu, R;
Zanasi, F;
(2023)
String Diagram Rewriting Modulo Commutative (Co)Monoid Structure.
In:
Proceedings of the 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023).
(pp. pp. 1-17).
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Preview |
PDF
LIPIcs-CALCO-2023-9.pdf - Published Version Download (837kB) | Preview |
Abstract
String diagrams constitute an intuitive and expressive graphical syntax that has found application in a very diverse range of fields including concurrency theory, quantum computing, control theory, machine learning, linguistics, and digital circuits. Rewriting theory for string diagrams relies on a combinatorial interpretation as double-pushout rewriting of certain hypergraphs. As previously studied, there is a “tension” in this interpretation: in order to make it sound and complete, we either need to add structure on string diagrams (in particular, Frobenius algebra structure) or pose restrictions on double-pushout rewriting (resulting in “convex” rewriting). From the string diagram viewpoint, imposing a full Frobenius structure may not always be natural or desirable in applications, which motivates our study of a weaker requirement: commutative monoid structure. In this work we characterise string diagram rewriting modulo commutative monoid equations, via a sound and complete interpretation in a suitable notion of double-pushout rewriting of hypergraphs.
| Type: | Proceedings paper |
|---|---|
| Title: | String Diagram Rewriting Modulo Commutative (Co)Monoid Structure |
| Event: | 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023) |
| ISBN-13: | 978-3-95977-287-7 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4230/LIPIcs.CALCO.2023.9 |
| Publisher version: | https://doi.org/10.4230/LIPIcs.CALCO.2023.9 |
| Language: | English |
| Additional information: | © The Authors 2023. Original content in this paper is licensed under the terms of the Creative Commons Attribution 4.0 International (CC BY 4.0) Licence (https://creativecommons.org/licenses/by/4.0/). |
| Keywords: | String diagrams, Double-pushout rewriting, Commutative monoid |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10178669 |
Archive Staff Only
 |
View Item |
