Document Open Access Logo

Regular Monoidal Languages

Authors Matthew Earnshaw , Paweł Sobociński

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.44.pdf
  • Filesize: 0.93 MB
  • 14 pages

Document Identifiers

Author Details

Matthew Earnshaw
  • Department of Software Science, Tallinn University of Technology, Estonia
Paweł Sobociński
  • Department of Software Science, Tallinn University of Technology, Estonia

Funding

This research was supported by the ESF funded Estonian IT Academy research measure (project 2014-2020.4.05.19- 0001). The second author was additionally supported by the Estonian Research Council grant PRG1210.

Acknowledgements

We would like to thank Ed Morehouse for extensive discussions concerning this work, and Tobias Heindel for discussion of his erstwhile project that partially inspired ours.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.MFCS.2022.44

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Categorical semantics
Keywords
  • monoidal categories
  • string diagrams
  • formal language theory
  • cartesian restriction categories

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mikołaj Bojańczyk, Bartek Klin, and Julian Salamanca. Monadic monadic second order logic, 2022. URL: https://doi.org/10.48550/ARXIV.2201.09969.
  2. Francis Bossut, Max Dauchet, and Bruno Warin. A Kleene theorem for a class of planar acyclic graphs. Inf. Comput., 117:251-265, March 1995. URL: https://doi.org/10.1006/inco.1995.1043.
  3. J.R.B. Cockett and Stephen Lack. Restriction categories I: categories of partial maps. Theoretical Computer Science, 270(1):223-259, 2002. URL: https://doi.org/10.1016/S0304-3975(00)00382-0.
  4. Robin Cockett and Stephen Lack. Restriction categories III: colimits, partial limits and extensivity. Mathematical Structures in Computer Science, 17(4):775-817, 2007. URL: https://doi.org/10.1017/S0960129507006056.
  5. Thomas Colcombet and Daniela Petrişan. Automata Minimization: a Functorial Approach. Logical Methods in Computer Science, Volume 16, Issue 1, March 2020. URL: https://doi.org/10.23638/LMCS-16(1:32)2020.
  6. Matthew Earnshaw and Paweł Sobociński. Regular monoidal languages, 2022. URL: https://doi.org/10.48550/ARXIV.2207.00526.
  7. Uli Fahrenberg, Christian Johansen, Georg Struth, and Krzysztof Ziemiański. Languages of higher-dimensional automata. Mathematical Structures in Computer Science, 31(5):575-613, 2021. URL: https://doi.org/10.1017/S0960129521000293.
  8. Richard Garner and Tom Hirschowitz. Shapely monads and analytic functors. Journal of Logic and Computation, 28(1):33-83, November 2017. URL: https://doi.org/10.1093/logcom/exx029.
  9. Ferenc Gécseg and Magnus Steinby. Tree automata, 2015. URL: https://doi.org/10.48550/ARXIV.1509.06233.
  10. T. Heindel. A Myhill-Nerode theorem beyond trees and forests via finite syntactic categories internal to monoids. Preprint, 2017. Google Scholar
  11. John Power and Edmund Robinson. Premonoidal categories and notions of computation. Mathematical Structures in Computer Science, 7(5), 1997. URL: https://doi.org/10.1017/S0960129597002375.
  12. Kimmo I. Rosenthal. Quantaloids, enriched categories and automata theory. Applied Categorical Structures, 3(3):279-301, 1995. URL: https://doi.org/10.1007/bf00878445.
  13. Paul W. K Rothemund, Nick Papadakis, and Erik Winfree. Algorithmic self-assembly of DNA Sierpinski triangles. PLOS Biology, 2(12), December 2004. URL: https://doi.org/10.1371/journal.pbio.0020424.
  14. Jacques Sakarovitch. Elements of automata theory. Cambridge University Press, Cambridge New York, 2009. Google Scholar
  15. P. Selinger. A survey of graphical languages for monoidal categories. In B. Coecke, editor, New Structures for Physics, pages 289-355. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-12821-9_4.
  16. Henning Urbat, Jiri Adámek, Liang-Ting Chen, and Stefan Milius. Eilenberg Theorems for Free. In Kim G. Larsen, Hans L. Bodlaender, and Jean-Francois Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), volume 83 of LIPIcs, pages 43:1-43:15, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.43.
  17. R.F.C. Walters. A note on context-free languages. Journal of Pure and Applied Algebra, 62(2):199-203, 1989. URL: https://doi.org/10.1016/0022-4049(89)90151-5.
  18. Vladimir Zamdzhiev. Rewriting Context-free Families of String Diagrams. PhD thesis, University of Oxford, 2016. Google Scholar
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