2026-07-23T05:44:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16842 2024-03-06T10:58:28Z ddc:004 open_access

Regular Monoidal Languages Earnshaw, Matthew Sobociński, Paweł monoidal categories string diagrams formal language theory cartesian restriction categories 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthew Earnshaw and Paweł Sobociński 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.44 urn:nbn:de:0030-drops-168425 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.44 eng https://creativecommons.org/licenses/by/4.0/legalcode