{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:55:49Z","timestamp":1790927749157,"version":"4.1.0"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T00:00:00Z","timestamp":1646870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Italian MIUR PRIN","award":["2017FTXR7S"],"award-info":[{"award-number":["2017FTXR7S"]}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/V002376\/1"],"award-info":[{"award-number":["EP\/V002376\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Estonian IT Academy research","award":["2014-2020.4.05.19-0001"],"award-info":[{"award-number":["2014-2020.4.05.19-0001"]}]},{"DOI":"10.13039\/501100002301","name":"Estonian Research Council","doi-asserted-by":"crossref","award":["PRG1210"],"award-info":[{"award-number":["PRG1210"]}],"id":[{"id":"10.13039\/501100002301","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>String diagrams are a powerful and intuitive graphical syntax, originating in theoretical physics and later formalised in the context of symmetric monoidal categories. In recent years, they have found application in the modelling of various computational structures, in fields as diverse as Computer Science, Physics, Control Theory, Linguistics, and Biology.<\/jats:p>\n                  <jats:p>In several of these proposals, transformations of systems are modelled as rewrite rules of diagrams. These developments require a mathematical foundation for string diagram rewriting: whereas rewrite theory for terms is well-understood, the two-dimensional nature of string diagrams poses quite a few additional challenges.<\/jats:p>\n                  <jats:p>This work systematises and expands a series of recent conference papers, laying down such a foundation. As a first step, we focus on the case of rewrite systems for string diagrammatic theories that feature a Frobenius algebra. This common structure provides a more permissive notion of composition than the usual one available in monoidal categories, and has found many applications in areas such as concurrency, quantum theory, and electrical circuits. Notably, this structure provides an exact correspondence between the syntactic notion of string diagrams modulo Frobenius structure and the combinatorial structure of hypergraphs.<\/jats:p>\n                  <jats:p>Our work introduces a combinatorial interpretation of string diagram rewriting modulo Frobenius structures in terms of double-pushout hypergraph rewriting. We prove this interpretation to be sound and complete and we also show that the approach can be generalised to rewriting modulo multiple Frobenius structures. As a proof of concept, we show how to derive from these results a termination strategy for Interacting Bialgebras, an important rewrite theory in the study of quantum circuits and signal flow graphs.<\/jats:p>","DOI":"10.1145\/3502719","type":"journal-article","created":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T10:48:18Z","timestamp":1646909298000},"page":"1-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["String Diagram Rewrite Theory I: Rewriting with Frobenius Structure"],"prefix":"10.1145","volume":"69","author":[{"given":"Filippo","family":"Bonchi","sequence":"first","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabio","family":"Gadducci","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleks","family":"Kissinger","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pawel","family":"Sobocinski","sequence":"additional","affiliation":[{"name":"Tallinn University of Technology, Tallinn, Estonia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6457-1345","authenticated-orcid":false,"given":"Fabio","family":"Zanasi","sequence":"additional","affiliation":[{"name":"University College London, London, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,3,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/1018438.1021878"},{"key":"e_1_3_2_3_2","article-title":"Cospans and spans of graphs: A categorical algebra for the sequential and parallel composition of discrete systems","author":"Albasini Luisa","year":"2009","unstructured":"Luisa Albasini, Nicoletta Sabadini, and Robert F. C. Walters. 2009. Cospans and spans of graphs: A categorical algebra for the sequential and parallel composition of discrete systems. arXiv:0909.4136. Retrieved from https:\/\/arxiv.org\/abs\/0909.4136.","journal-title":"arXiv:0909.4136"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90003-0"},{"key":"e_1_3_2_5_2","article-title":"PROPs in network theory","author":"Baez John","year":"2017","unstructured":"John Baez, Brandon Coya, and Franciscus Rebro. 2017. PROPs in network theory. arXiv:1707.08321. Retrieved from https:\/\/arxiv.org\/abs\/1707.08321.","journal-title":"arXiv:1707.08321"},{"key":"e_1_3_2_6_2","first-page":"836","article-title":"Categories in control","volume":"30","author":"Baez John","year":"2015","unstructured":"John Baez and Jason Erbele. 2015. Categories in control. Theory and Application of Categories 30 (2015), 836\u2013881.","journal-title":"Theory and Application of Categories"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-17945-3_8"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BFb0074298","volume-title":"Reports of the Midwest Category Seminar","author":"B\u00e9nabou Jean","year":"1967","unstructured":"Jean B\u00e9nabou. 1967. Introduction to bicategories. Reports of the Midwest Category Seminar. Vol. 47. Springer, 1\u201377."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935316"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","unstructured":"Filippo Bonchi Fabio Gadducci Aleks Kissinger Pawel Soboci\u0144ski and Fabio Zanasi. 2018. Rewriting with Frobenius. In Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science . Anuj Dawar and Erich Gr\u00e4del (Eds.). ACM 165\u2013174.","DOI":"10.1145\/3209108.3209137"},{"key":"e_1_3_2_11_2","article-title":"String diagram rewrite theory II: Rewriting with symmetric monoidal structure","author":"Bonchi Filippo","year":"2020","unstructured":"Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Soboci\u0144ski, and Fabio Zanasi. 2020. String diagram rewrite theory II: Rewriting with symmetric monoidal structure. arXiv:2104.14686. Retrieved from https:\/\/arxiv.org\/abs\/2104.14686.","journal-title":"arXiv:2104.14686"},{"key":"e_1_3_2_12_2","article-title":"String diagram rewrite theory III: Confluence with and without Frobenius","author":"Bonchi Filippo","year":"2021","unstructured":"Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Soboci\u0144ski, and Fabio Zanasi. 2021. String diagram rewrite theory III: Confluence with and without Frobenius. arXiv:2109.06049. Retrieved from https:\/\/arxiv.org\/abs\/2109.06049.","journal-title":"arXiv:2109.06049"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_6"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.10.005"},{"key":"e_1_3_2_15_2","first-page":"24:1\u201324:16","volume-title":"Proceedings of the 28th International Conference on Concurrency Theory","volume":"85","author":"Bonchi Filippo","year":"2017","unstructured":"Filippo Bonchi, Joshua Holland, Dusko Pavlovic, and Pawel Soboci\u0144ski. 2017. Refinement for signal flow graphs. In Proceedings of the 28th International Conference on Concurrency Theory. Roland Meyer and Uwe Nestmann (Eds.), Vol. 85. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 24:1\u201324:16."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3290338"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","unstructured":"Filippo Bonchi Robin Piedeleu Pawel Soboci\u0144ski and Fabio Zanasi. 2019. Graphical affine algebra. In Proceedings of the 34th Annual ACM\/IEEE Symposium on Logic in Computer Science . IEEE 1\u201312.","DOI":"10.1109\/LICS.2019.8785877"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54830-7_23"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676993"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.03.002"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2016.06.002"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44584-6_30"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","unstructured":"Roberto Bruni and Fabio Gadducci. 2001. Some algebraic laws for spans (and their connections with multirelations). Proceedings of Relational Methods in Software . Wolfram Kahl David L. Parnas and Gunther Schmidt (Eds.) Vol. 44(3). Elsevier 175\u2013193.","DOI":"10.1016\/S1571-0661(04)80937-X"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90054-W"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(87)90121-6"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_25"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781316219317"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129512000047"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/278918.278928"},{"key":"e_1_3_2_30_2","first-page":"243","volume-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics","author":"Dershowitz Nachum","year":"1990","unstructured":"Nachum Dershowitz and Jean-Pierre Jouannaud. 1990. Rewrite systems. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics. Jan van Leeuwen (Ed.). Elsevier and MIT Press, 243\u2013320."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.26.16"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129512000138"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24727-2_12"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2019.02.014"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1017\/S096012950700610X"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-64299-4_36"},{"key":"e_1_3_2_37_2","volume-title":"Proceedings of the Third International Workshop on Graph Computation Models","volume":"39","author":"Heum\u00fcller Marvin","year":"2011","unstructured":"Marvin Heum\u00fcller, Salil Joshi, Barbara K\u00f6nig, and Jan St\u00fcckrath. 2011. Construction of pushout complements in the category of hypergraphs. In Proceedings of the Third International Workshop on Graph Computation Models. Rachid Echahed, Annegret Habel, and Mohamed Mosbah (Eds.), Vol. 39. EASST."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322230"},{"key":"e_1_3_2_39_2","first-page":"437","volume-title":"Computation, Meaning, and Logic","author":"Hyland Martin","year":"2007","unstructured":"Martin Hyland and John Power. 2007. The category theoretic understanding of universal algebra: Lawvere theories and monads. In Computation, Meaning, and Logic. Luca Cardelli, Marcelo P. Fiore, and Glynn Winskel (Eds.), Vol. 172. Elsevier, 437\u2013458."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209139"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(91)90003-P"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100074338"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/2464830"},{"key":"e_1_3_2_44_2","article-title":"Finite matrices are complete for (dagger-)hypergraph categories","author":"Kissinger Aleks","year":"2014","unstructured":"Aleks Kissinger. 2014. Finite matrices are complete for (dagger-)hypergraph categories. arXiv1406.5942. Retrieved from https:\/\/arxiv.org\/abs\/1406.5942.","journal-title":"arXiv1406.5942"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.318.14"},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","unstructured":"Aleks Kissinger and Vladimir Zamdzhiev. 2015. Quantomatic: A proof assistant for diagrammatic reasoning. In Proceedings of the 25th International Conference on Automated Deduction . Amy P. Felty and Aart Middeldorp (Eds.) Vol. 9195. Springer 326\u2013336.","DOI":"10.1007\/978-3-319-21401-6_22"},{"key":"e_1_3_2_47_2","first-page":"263","volume-title":"Proceedings of the Computational Problems in Abstract Algebra","author":"Knuth Donald E.","year":"1970","unstructured":"Donald E. Knuth and Peter B. Bendix. 1970. Simple word problems in universal algebras. In Proceedings of the Computational Problems in Abstract Algebra. Pergamon Press, 263\u2013297."},{"issue":"9","key":"e_1_3_2_48_2","first-page":"147","article-title":"Composing PROPs","volume":"13","author":"Lack Steve","year":"2004","unstructured":"Steve Lack. 2004. Composing PROPs. Theory and Application of Categories 13, 9 (2004), 147\u2013163.","journal-title":"Theory and Application of Categories"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005028"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(03)00069-0"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1965-11234-4"},{"key":"e_1_3_2_52_2","volume-title":"Categories for the Working Mathematician","author":"Lane Saunders Mac","year":"1998","unstructured":"Saunders Mac Lane. 1998. Categories for the Working Mathematician. Springer."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-2009-030-5"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-10(2:1)2014"},{"key":"e_1_3_2_55_2","article-title":"A universal completion of the ZX-calculus","author":"Ng Kang Feng","year":"2017","unstructured":"Kang Feng Ng and Quanlong Wang. 2017. A universal completion of the ZX-calculus. arXiv:1706.09877. Retrieved from https:\/\/arxiv.org\/abs\/1706.09877.","journal-title":"arXiv:1706.09877"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/322248.322251"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1142\/9789812815149_0001"},{"key":"e_1_3_2_58_2","volume-title":"Manipulation of Graphs, Algebras and Pictures","author":"Plump Detlef","year":"2010","unstructured":"Detlef Plump. 2010. Checking graph-transformation systems for confluence. In Manipulation of Graphs, Algebras and Pictures. Frank Drewes, Annegret Habel, Berthold Hoffmann, and Detlef Plump (Eds.), Vol. 26. EASST."},{"issue":"6","key":"e_1_3_2_59_2","first-page":"164","article-title":"Generic commutative separable algebras and cospans of graphs","volume":"17","author":"Rosebrugh Robert","year":"2005","unstructured":"Robert Rosebrugh, Nicoletta Sabadini, and R. F. C. Walters. 2005. Generic commutative separable algebras and cospans of graphs. Theory and Application of Categories 17, 6 (2005), 164\u2013177.","journal-title":"Theory and Application of Categories"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.40"},{"key":"e_1_3_2_61_2","first-page":"151","volume-title":"Proceedings of the 7th International Conference on Quantum Physics and Logic","author":"Selinger Peter","year":"2010","unstructured":"Peter Selinger. 2010. Autonomous categories in which A = A \\( ^* \\) . In Proceedings of the 7th International Conference on Quantum Physics and Logic. 151\u2013160."},{"issue":"813","key":"e_1_3_2_62_2","first-page":"289","article-title":"A survey of graphical languages for monoidal categories","volume":"13","author":"Selinger Peter","year":"2011","unstructured":"Peter Selinger. 2011. A survey of graphical languages for monoidal categories. Springer Lecture Notes in Physics 13, 813 (2011), 289\u2013355.","journal-title":"Springer Lecture Notes in Physics"},{"key":"e_1_3_2_63_2","unstructured":"Pawel Sobocinski. Graphical Linear Algebra. Retrieved from https:\/\/graphicallinearalgebra.net\/."},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)00270-1"},{"key":"e_1_3_2_65_2","volume-title":"Interacting Hopf Algebras: The Theory of Linear Systems","author":"Zanasi Fabio","year":"2015","unstructured":"Fabio Zanasi. 2015. Interacting Hopf Algebras: The Theory of Linear Systems. Ph.D. Dissertation. \u00c9cole Normale Sup\u00e9rieure de Lyon."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502719","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3502719","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T14:09:47Z","timestamp":1750169387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502719"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,10]]},"references-count":64,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3502719"],"URL":"https:\/\/doi.org\/10.1145\/3502719","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,10]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}