Aleksandar Milosavljevic ; Robin Piedeleu ; Fabio Zanasi - Rewriting for Symmetric Monoidal Categories with Commutative (Co)Monoid Structure

lmcs:14937 - Logical Methods in Computer Science, January 31, 2025, Volume 21, Issue 1 - https://doi.org/10.46298/lmcs-21(1:12)2025
Rewriting for Symmetric Monoidal Categories with Commutative (Co)Monoid StructureArticle

Authors: Aleksandar Milosavljevic ; Robin Piedeleu ; Fabio Zanasi

    String diagrams are pictorial representations for morphisms of symmetric monoidal categories. They constitute an intuitive and expressive graphical syntax, which 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.


    Volume: Volume 21, Issue 1
    Published on: January 31, 2025
    Accepted on: December 15, 2024
    Submitted on: December 13, 2024
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Category Theory

    Consultation statistics

    This page has been seen 96 times.
    This article's PDF has been downloaded 57 times.