2 Search Results for "Earnshaw, Matthew"

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-dev.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-dev.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}
}
  • Refine by Author
  • 2 Earnshaw, Matthew
  • 2 Sobociński, Paweł

  • Refine by Classification
  • 2 Theory of computation → Categorical semantics
  • 2 Theory of computation → Formal languages and automata theory
  • 1 Theory of computation → Concurrency

  • Refine by Keyword
  • 1 Mazurkiewicz traces
  • 1 asynchronous automata
  • 1 cartesian restriction categories
  • 1 formal language theory
  • 1 monoidal categories
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact