Document Open Access Logo

String Diagram Rewriting Modulo Commutative (Co)Monoid Structure

Authors Aleksandar Milosavljević, Robin Piedeleu , Fabio Zanasi

PDF

File

Thumbnail PDF
PDF
LIPIcs.CALCO.2023.9.pdf
  • Filesize: 0.79 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Rewrite systems
Keywords
  • String diagrams
  • Double-pushout rewriting
  • Commutative monoid

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Aleksandar Milosavljević, Robin Piedeleu, and Fabio Zanasi. String Diagram Rewriting Modulo Commutative (Co)Monoid Structure. In 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 270, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CALCO.2023.9

Author Details

Aleksandar Milosavljević
  • University College London, UK
Robin Piedeleu
  • University College London, UK
Fabio Zanasi
  • University College London, UK
  • University of Bologna, Italy

Funding

RP and FZ acknowledge support from epsrc grant EP/V002376/1.

Acknowledgements

We thank Tobias Fritz for helpful discussion and the anonymous reviewers of CALCO for their suggestions.

References

  1. John Baez and Jason Erbele. Categories in control. Theory and Applications of Categories, 30:836-881, 2015. URL: http://arxiv.org/abs/1405.6881.
  2. C. Berge. Graphs and Hypergraphs. Elsevier Science Ltd., GBR, 1985. Google Scholar
  3. Guillaume Boisseau and Pawel Sobocinski. String diagrammatic electrical circuit theory. In ACT, volume 372 of EPTCS, pages 178-191, 2021. Google Scholar
  4. Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski, and Fabio Zanasi. Rewriting modulo symmetric monoidal structure. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 710-719. ACM, 2016. URL: https://doi.org/10.1145/2933575.2935316.
  5. Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski, and Fabio Zanasi. String diagram rewrite theory I: Rewriting with Frobenius structure, 2020. URL: https://doi.org/10.48550/ARXIV.2012.01847.
  6. Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski, and Fabio Zanasi. String diagram rewrite theory II: Rewriting with symmetric monoidal structure, 2021. URL: https://doi.org/10.48550/ARXIV.2104.14686.
  7. Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Paweł Sobociński, and Fabio Zanasi. String diagram rewrite theory III: Confluence with and without Frobenius, 2021. URL: https://doi.org/10.48550/ARXIV.2109.06049.
  8. Filippo Bonchi, Joshua Holland, Dusko Pavlovic, and Pawel Sobocinski. Refinement for signal flow graphs. In CONCUR, volume 85 of LIPIcs, pages 24:1-24:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  9. Filippo Bonchi, Joshua Holland, Robin Piedeleu, Pawel Sobocinski, and Fabio Zanasi. Diagrammatic algebra: from linear to concurrent systems. Proc. ACM Program. Lang., 3(POPL):25:1-25:28, 2019. URL: https://doi.org/10.1145/3290338.
  10. Filippo Bonchi, Robin Piedeleu, Pawel Sobocinski, and Fabio Zanasi. Graphical affine algebra. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019, pages 1-12. IEEE, 2019. URL: https://doi.org/10.1109/LICS.2019.8785877.
  11. Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi. Deconstructing Lwvere with distributive laws. J. Log. Algebraic Methods Program., 95:128-146, 2018. Google Scholar
  12. Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi. A survey of compositional signal flow theory. In IFIP’s Exciting First 60+ Years, volume 600 of IFIP Advances in Information and Communication Technology, pages 29-56. Springer, 2021. Google Scholar
  13. Aurelio Carboni and R. F. C. Walters. Cartesian bicategories I. J Pure Appl Algebra, 49:11-32, 1987. Google Scholar
  14. A. Corradini, Ugo Montanari, Francesca Rossi, H. Ehrig, Reiko Heckel, and Michael Löwe. Basic concepts and double pushout approach. Algebraic Approaches to Graph Transformation, pages 163-246, January 1997. Google Scholar
  15. Geoffrey S. H. Cruttwell, Bruno Gavranovic, Neil Ghani, Paul W. Wilson, and Fabio Zanasi. Categorical foundations of gradient-based learning. In ESOP, volume 13240 of Lecture Notes in Computer Science, pages 1-28. Springer, 2022. Google Scholar
  16. Hartmut Ehrig and Barbara König. Deriving bisimulation congruences in the DPO approach to graph rewriting. In Igor Walukiewicz, editor, Foundations of Software Science and Computation Structures, pages 151-166, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  17. Brendan Fong and Fabio Zanasi. Universal constructions for (co)relations: categories, monoidal categories, and props. Log. Methods Comput. Sci., 14(3), 2018. Google Scholar
  18. Tobias Fritz. A synthetic approach to markov kernels, conditional independence and theorems on sufficient statistics. Advances in Mathematics, 370:107239, August 2020. URL: https://doi.org/10.1016/j.aim.2020.107239.
  19. Tobias Fritz and Wendong Liang. Free gs-monoidal categories and free Markov categories, 2022. URL: https://doi.org/10.48550/ARXIV.2204.02284.
  20. Dan R. Ghica, Achim Jung, and Aliaume Lopez. Diagrammatic semantics for digital circuits. In Valentin Goranko and Mads Dam, editors, 26th EACSL Annual Conference on Computer Science Logic, CSL 2017, August 20-24, 2017, Stockholm, Sweden, volume 82 of LIPIcs, pages 24:1-24:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CSL.2017.24.
  21. Dan R. Ghica and George Kaye. Rewriting modulo traced comonoid structure. CoRR, abs/2302.09631, 2023. Google Scholar
  22. Bart Jacobs, Aleks Kissinger, and Fabio Zanasi. Causal inference via string diagram surgery: A diagrammatic approach to interventions and counterfactuals. Math. Struct. Comput. Sci., 31(5):553-574, 2021. Google Scholar
  23. Aleks Kissinger, John van de Wetering, and Renaud Vilmart. Classical simulation of quantum circuits with partial and graphical stabiliser decompositions, 2022. URL: https://doi.org/10.48550/ARXIV.2202.09202.
  24. Stephen Lack. Composing props. Theory and Applications of Categories, 13(9):147-163, 2004. Google Scholar
  25. Stephen Lack and Paweł Sobociński. Adhesive and quasiadhesive categories. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 39(3):511-545, 2005. URL: https://doi.org/10.1051/ita:2005028.
  26. Aleksandar Milosavljevic, Robin Piedeleu, and Fabio Zanasi. String diagram rewriting modulo commutative (co)monoid structure. arXiv:2204.04274, 2023. Google Scholar
  27. Koko Muroya and Dan R. Ghica. The dynamic geometry of interaction machine: A token-guided graph rewriter. Log. Methods Comput. Sci., 15(4), 2019. Google Scholar
  28. Robin Piedeleu and Fabio Zanasi. An introduction to string diagrams for computer scientists. arXiv:2305.08768, 2023. Google Scholar
  29. Mehrnoosh Sadrzadeh, Stephen Clark, and Bob Coecke. The Frobenius anatomy of word meanings I: subject and object relative pronouns. J. Log. Comput., 23(6):1293-1317, 2013. Google Scholar
  30. Fabio Zanasi. Interacting Hopf Algebras- the Theory of Linear Systems. (Interacting Hopf Algebras - la théorie des systèmes linéaires). PhD thesis, École normale supérieure de Lyon, France, 2015. URL: https://tel.archives-ouvertes.fr/tel-01218015.
  31. Fabio Zanasi. Rewriting in free hypergraph categories. In GaM@ETAPS, volume 263 of EPTCS, pages 16-30, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact