Document Open Access Logo

Syntactic Monoids in a Category

Authors Jiri Adamek, Stefan Milius, Henning Urbat

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2015.1.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Jiri Adamek
Stefan Milius
Henning Urbat

Cite AsGet BibTex

Jiri Adamek, Stefan Milius, and Henning Urbat. Syntactic Monoids in a Category. In 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CALCO.2015.1

Abstract

The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category D. This allows for a uniform treatment of several notions of syntactic algebras known in the literature, including the syntactic monoids of Rabin and Scott (D = sets), the syntactic semirings of Polák (D = semilattices), and the syntactic associative algebras of Reutenauer (D = vector spaces). Assuming that D is a commutative variety of algebras, we prove that the syntactic D-monoid of a language L can be constructed as a quotient of a free D-monoid modulo the syntactic congruence of L, and that it is isomorphic to the transition D-monoid of the minimal automaton for L in D. Furthermore, in the case where the variety D is locally finite, we characterize the regular languages as precisely the languages with finite syntactic D-monoids.
Keywords
  • Syntactic monoid
  • transition monoid
  • algebraic automata theory
  • duality
  • coalgebra
  • algebra
  • symmetric monoidal closed category
  • commutative variety

Metrics

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

References

  1. Jiř\'ıAdámek, Stefan Milius, , and Henning Urbat. Syntactic monoids in a category. Extended version. http://arxiv.org/abs/1504.02694, 2015.
  2. Jiř\'ıAdámek, Stefan Milius, Robert S. R. Myers, and Henning Urbat. Generalized Eilenberg Theorem I: Local Varieties of Languages. In Anca Muscholl, editor, Proc. Foundations of Software Science and Computation Structures (FoSSaCS), volume 8412 of Lecture Notes Comput. Sci., pages 366-380. Springer, 2014. Google Scholar
  3. Jiř\'ıAdámek, Stefan Milius, Robert S. R. Myers, and Henning Urbat. On continuous nondeterminism and state minimality. In Bart Jacobs, Alexandra Silva, and Sam Staton, editors, Proc. Mathematical Foundations of Programming Science (MFPS XXX), volume 308 of Electron. Notes Theor. Comput. Sci., pages 3-23. Elsevier, 2014. Google Scholar
  4. Jiř\'ıAdámek, Stefan Milius, Robert S. R. Myers, and Henning Urbat. Varieties of Languages in a Category. Accepted for LICS 2015. http://arxiv.org/abs/1501.05180, 2015.
  5. A. Ballester-Bolinches, E. Cosme-Llopez, and J.J.M.M. Rutten. The dual equivalence of equations and coequations for automata. Technical report, CWI, 2014. Google Scholar
  6. Bernhard Banaschweski and Evelyn Nelson. Tensor products and bimorphisms. Canad. Math. Bull., 19:385-402, 1976. Google Scholar
  7. Nick Bezhanishvili, Clemens Kupke, and Prakash Panangaden. Minimization via duality. In Luke Ong and Ruy de Queiroz, editors, Logic, Language, Information and Computation, volume 7456 of Lecture Notes in Computer Science, pages 191-205. Springer Berlin Heidelberg, 2012. Google Scholar
  8. Mikołaj Bojánczyk. Recognisable languages over monads. Preprint: http://arxiv.org/abs/1502.04898, 2015.
  9. Mikołaj Bojánczyk and Igor Walukiewicz. Forest algebras. In Automata and Logic: History and Perspectives, pages 107-132, 2006. Google Scholar
  10. Marcello M. Bonsangue, Stefan Milius, and Alexandra Silva. Sound and complete axiomatizations of coalgebraic language equivalence. ACM Trans. Comput. Log., 14(1:7), 2013. Google Scholar
  11. Mai Gehrke, Serge Grigorieff, and Jean-Éric Pin. Duality and equational theory of regular languages. In Proc. ICALP 2008, Part II, volume 5126 of Lecture Notes Comput. Sci., pages 246-257. Springer, 2008. Google Scholar
  12. Joseph A. Goguen. Discrete-time machines in closed monoidal categories. I. J. Comput. Syst. Sci., 10(1):1-43, 1975. Google Scholar
  13. Anders Kock. Monads on symmetric monoidal closed categories. Arch. Math., 21:1-10, 1970. Google Scholar
  14. Saunders Mac Lane. Categories for the working mathematician. Springer, 2nd edition, 1998. Google Scholar
  15. Fred Linton. Autonomous equational categories. J. Math. Mech., 15:637-642, 166. Google Scholar
  16. Robert S. R. Myers, Jiř\'ıAdámek, Stefan Milius, and Henning Urbat. Canonical nondeterministic automata. In Marcello M. Bonsangue, editor, Proc. Coalgebraic Methods in Computer Science (CMCS'14), volume 8446 of Lecture Notes Comput. Sci., pages 189-210. Springer, 2014. Google Scholar
  17. Jean-Éric Pin. Mathematical foundations of automata theory. available at http://www.liafa.jussieu.fr/~jep/PDF/MPRI/MPRI.pdf, January 2015.
  18. Libor Polák. Syntactic semiring of a language. In Jiř\'ıSgall, Aleš Pultr, and Petr Kolman, editors, Proc. International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 2136 of Lecture Notes Comput. Sci., pages 611-620. Springer, 2001. Google Scholar
  19. Michael O. Rabin and Dana S. Scott. Finite automata and their decision problems. IBM J. Res. Dev., 3(2):114-125, April 1959. Google Scholar
  20. Christophe Reutenauer. Séries formelles et algèbres syntactiques. J. Algebra, 66:448-483, 1980. Google Scholar
  21. Jan J. M. M. Rutten. Universal coalgebra: a theory of systems. Theoret. Comput. Sci., 249(1):3-80, 2000. Google Scholar
  22. Thomas Wilke. An Eilenberg Theorem for Infinity-Languages. In Proc. ICALP 91, pages 588-599. Springer, 1991. 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