2026-07-23T04:16:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18577 2024-03-06T11:02:10Z ddc:004 open_access

String Diagrammatic Trace Theory Earnshaw, Matthew Sobociński, Paweł symmetric monoidal categories Mazurkiewicz traces asynchronous automata We extend the theory of formal languages in monoidal categories to the multi-sorted, symmetric case, and show how this theory permits a graphical treatment of topics in concurrency. In particular, we show that Mazurkiewicz trace languages are precisely symmetric monoidal languages over monoidal distributed alphabets. We introduce symmetric monoidal automata, which define the class of regular symmetric monoidal languages. Furthermore, we prove that Zielonka’s asynchronous automata coincide with symmetric monoidal automata over monoidal distributed alphabets. Finally, we apply the string diagrams for symmetric premonoidal categories to derive serializations of traces. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthew Earnshaw and Paweł Sobociński 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.43 urn:nbn:de:0030-drops-185770 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.43 eng https://creativecommons.org/licenses/by/4.0/legalcode