2026-08-08T16:10:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18806 2024-03-06T11:01:54Z ddc:004 open_access

String Diagram Rewriting Modulo Commutative (Co)Monoid Structure Milosavljević, Aleksandar Piedeleu, Robin Zanasi, Fabio String diagrams Double-pushout rewriting Commutative monoid 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aleksandar Milosavljević and Robin Piedeleu and Fabio Zanasi 2023 Is Part Of LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CALCO.2023.9 urn:nbn:de:0030-drops-188067 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.9 eng https://creativecommons.org/licenses/by/4.0/legalcode