Document Open Access Logo

Eilenberg Theorems for Free

Authors Henning Urbat, Jiri Adámek, Liang-Ting Chen, Stefan Milius

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.43.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Henning Urbat
Jiri Adámek
Liang-Ting Chen
Stefan Milius

Cite AsGet BibTex

Henning Urbat, Jiri Adámek, Liang-Ting Chen, and Stefan Milius. Eilenberg Theorems for Free. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.43

Abstract

Eilenberg-type correspondences, relating varieties of languages (e.g., of finite words, infinite words, or trees) to pseudovarieties of finite algebras, form the backbone of algebraic language theory. We show that they all arise from the same recipe: one models languages and the algebras recognizing them by monads on an algebraic category, and applies a Stone-type duality. Our main contribution is a variety theorem that covers e.g. Wilke's and Pin's work on infinity-languages, the variety theorem for cost functions of Daviaud, Kuperberg, and Pin, and unifies the two categorical approaches of Bojanczyk and of Adamek et al. In addition we derive new results, such as an extension of the local variety theorem of Gehrke, Grigorieff, and Pin from finite to infinite words.
Keywords
  • Eilenberg's theorem
  • variety of languages
  • pseudovariety
  • monad
  • duality

Metrics

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

References

  1. J. Adámek, S. Milius, R. Myers, and H. Urbat. Generalized Eilenberg Theorem I: Local Varieties of Languages. In A. Muscholl, editor, Proc. FoSSaCS'14, volume 8412 of LNCS, pages 366-380. Springer, 2014. Full version: URL: http://arxiv.org/pdf/1501.02834v1.pdf.
  2. J. Adámek, S. Milius, and H. Urbat. Syntactic monoids in a category. In Proc. CALCO'15, LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. Full version: URL: http://arxiv.org/abs/1504.02694.
  3. J. Adámek, R. Myers, S. Milius, and H. Urbat. Varieties of languages in a category. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE, 2015. Google Scholar
  4. J. Almeida. On pseudovarieties, varieties of languages, filters of congruences, pseudoidentities and related topics. Algebra Universalis, 27(3):333-350, 1990. Google Scholar
  5. N. Bedon and O. Carton. An Eilenberg theorem for words on countable ordinals. In Proc. LATIN'98, volume 1380 of LNCS, pages 53-64. Springer, 1998. Google Scholar
  6. N. Bedon and C. Rispal. Schützenberger and Eilenberg theorems for words on linear orderings. In Proc. DLT'05, volume 3572 of LNCS, pages 134-145. Springer, 2005. Google Scholar
  7. G. Birkhoff. Rings of sets. Duke Mathematical Journal, 3(3):443-454, 1937. Google Scholar
  8. M. Bojańczyk. Recognisable languages over monads. In I. Potapov, editor, Proc. DLT'15, volume 9168 of LNCS, pages 1-13. Springer, 2015. URL: http://arxiv.org/abs/1502.04898.
  9. L.-T. Chen, J. Adámek, S. Milius, and H. Urbat. Profinite monads, profinite equations and Reiterman’s theorem. In B. Jacobs and C. Löding, editors, Proc. FoSSaCS'16, volume 9634 of LNCS. Springer, 2016. URL: http://arxiv.org/abs/1511.02147.
  10. L.-T. Chen and H. Urbat. A fibrational approach to automata theory. In L. S. Moss and P. Sobocinski, editors, Proc. CALCO'15, LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. Google Scholar
  11. L. Daviaud, D. Kuperberg, and J.-É. Pin. Varieties of cost functions. In N. Ollinger and H. Vollmer, editors, Proc. STACS 2016, volume 47 of LIPIcs, pages 30:1-30:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016. Google Scholar
  12. S. Eilenberg. Automata, Languages, and Machines Vol. B. Academic Press, 1976. Google Scholar
  13. M. J. Gabbay, T. Litak, and D. Petrişan. Stone duality for nominal boolean algebras with new. In A. Corradini, B. Klin, and C. Cîrstea, editors, Proc. CALCO'11, volume 6859 of LNCS, pages 192-207. Springer, 2011. Google Scholar
  14. M. Gehrke, S. Grigorieff, and J.-É. Pin. Duality and equational theory of regular languages. In L. Aceto and al., editors, Proc. ICALP'08, Part II, volume 5126 of LNCS, pages 246-257. Springer, 2008. Google Scholar
  15. P. T. Johnstone. Stone spaces. Cambridge University Press, 1982. Google Scholar
  16. E. G. Manes. Algebraic Theories, volume 26 of Graduate Texts in Mathematics. Springer, 1976. Google Scholar
  17. G. Matthiessen. Theorie der heterogenen Algebren. Technical report, Universität Bremen, 1976. Google Scholar
  18. G. Matthiessen. A heterogeneous algebraic approach to some problems in automata theory, many-valued logic and other topics. In Proc. Klagenfurt Conf., 1979. Google Scholar
  19. D. Perrin and J.-É. Pin. Infinite Words. Elsevier, 2004. Google Scholar
  20. J.-É. Pin. A variety theorem without complementation. Russ. Math., 39:80-90, 1995. Google Scholar
  21. J.-É. Pin. Positive varieties and infinite words. In LATIN 98, volume 1380 of LNCS, pages 76-87. Springer, 1998. Google Scholar
  22. J.-É. Pin. Mathematical foundations of automata theory. Available at http://www.liafa.jussieu.fr/~jep/PDF/MPRI/MPRI.pdf, November 2016.
  23. N. Pippenger. Regular languages and Stone duality. Th. Comp. Sys., 30(2):121-134, 1997. URL: http://link.springer.com/10.1007/BF02679444, URL: http://dx.doi.org/10.1007/BF02679444.
  24. L. Polák. Syntactic semiring of a language. In J. Sgall, A. Pultr, and P. Kolman, editors, Proc. MFCS'01, volume 2136 of LNCS, pages 611-620. Springer, 2001. Google Scholar
  25. J. Reiterman. The Birkhoff theorem for finite algebras. Algebra Universalis, 14(1):1-10, 1982. Google Scholar
  26. C. Reutenauer. Séries formelles et algèbres syntactiques. J. Algebra, 66:448-483, 1980. Google Scholar
  27. J. Salamánca. Unveiling Eilenberg-type Correspondences: Birkhoff’s Theorem for (finite) Algebras + Duality. https://arxiv.org/abs/1702.02822, February 2017.
  28. S. Salehi and M. Steinby. Varieties of many-sorted recognizable sets. TUCS Technical Report 626, Turku Center for Computer Science, 2004. Google Scholar
  29. S. Salehi and M. Steinby. Tree algebras and varieties of tree languages. Theor. Comput. Sci., 377(1-3):1-24, 2007. Google Scholar
  30. M. P. Schützenberger. On finite monoids having only trivial subgroups. Inform. and Control, 8:190-194, 1965. Google Scholar
  31. H. Straubing. On logical descriptions of regular languages. In S. Rajsbaum, editor, LATIN 2002 Theor. Informatics, volume 2286 of LNCS, pages 528-538. Springer, 2002. Google Scholar
  32. D. Thérien. Classification of Regular Languages by Congruences. PhD thesis, University of Waterloo, 1980. Google Scholar
  33. H. Urbat. A note on HSP theorems. URL: https://www.tu-braunschweig.de/Medien-DB/iti/hspnote.pdf.
  34. H. Urbat, J. Adámek, L.-T. Chen, and S. Milius. Eilenberg Theorems for Free. https://arxiv.org/abs/1602.05831. February 2017.
  35. T. Wilke. An Eilenberg theorem for ∞-languages. In Proc. ICALP'91, volume 510 of LNCS, 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