DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2023.43

String Diagrammatic Trace Theory

Authors: Matthew Earnshaw and Paweł Sobociński

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

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.

Cite as

Matthew Earnshaw and Paweł Sobociński. String Diagrammatic Trace Theory. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{earnshaw_et_al:LIPIcs.MFCS.2023.43,
  author =	{Earnshaw, Matthew and Soboci\'{n}ski, Pawe{\l}},
  title =	{{String Diagrammatic Trace Theory}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.43},
  URN =		{urn:nbn:de:0030-drops-185770},
  doi =		{10.4230/LIPIcs.MFCS.2023.43},
  annote =	{Keywords: symmetric monoidal categories, Mazurkiewicz traces, asynchronous automata}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2022.44

Regular Monoidal Languages

Authors: Matthew Earnshaw and Paweł Sobociński

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

We introduce regular languages of morphisms in free monoidal categories, with their associated grammars and automata. These subsume the classical theory of regular languages of words and trees, but also open up a much wider class of languages over string diagrams. We use the algebra of monoidal categories to investigate the properties of regular monoidal languages, and provide sufficient conditions for their recognizability by deterministic monoidal automata.

Cite as

Matthew Earnshaw and Paweł Sobociński. Regular Monoidal Languages. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{earnshaw_et_al:LIPIcs.MFCS.2022.44,
  author =	{Earnshaw, Matthew and Soboci\'{n}ski, Pawe{\l}},
  title =	{{Regular Monoidal Languages}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.44},
  URN =		{urn:nbn:de:0030-drops-168425},
  doi =		{10.4230/LIPIcs.MFCS.2022.44},
  annote =	{Keywords: monoidal categories, string diagrams, formal language theory, cartesian restriction categories}
}

Search Results

Documents authored by Earnshaw, Matthew

String Diagrammatic Trace Theory

Abstract

Cite as

Regular Monoidal Languages

Abstract

Cite as

Thanks for your feedback!

Could not send message