1. String Diagrammatic Trace Theory
- Author
-
Earnshaw, Matthew and Sobociński, Paweł
- Subjects
Computer Science - Formal Languages and Automata Theory ,Mathematics - Category Theory - Abstract
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., Comment: Paper accepted for MFCS 2023
- Published
- 2023