Eilenberg theorems for free. (English) Zbl 1441.68139
Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 43, 15 p. (2017).
Summary: 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. T. Wilke’s [Lect. Notes Comput. Sci. 510, 588–599 (1991; Zbl 0766.68083)] and J.-É. Pin’s [Lect. Notes Comput. Sci. 1380, 76–87 (1998; Zbl 0909.20051)] work on \(\infty\)-languages, the variety theorem for cost functions of L. Daviaud et al. [LIPIcs – Leibniz Int. Proc. Inform. 47, Article 30, 14 p. (2016; Zbl 1388.68192)], and unifies the two categorical approaches of M. Bojańczyk [Lect. Notes Comput. Sci. 9168, 1–13 (2015; Zbl 1434.68307)] and of the first author et al. [Lect. Notes Comput. Sci. 8412, 366–380 (2014; Zbl 1407.68314); LIPIcs – Leibniz Int. Proc. Inform. 35, 1–16 (2015; Zbl 1366.68188); in: Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015. Los Alamitos, CA: IEEE Computer Society. 414–425 (2015; Zbl 1401.68212)]. In addition we derive new results, such as an extension of the local variety theorem of M. Gehrke et al. [Lect. Notes Comput. Sci. 5126, 246–257 (2008; Zbl 1165.68049)] from finite to infinite words.
For the entire collection see [Zbl 1376.68011].
For the entire collection see [Zbl 1376.68011].
MSC:
| 68Q70 | Algebraic theory of languages and automata |
Citations:
Zbl 0766.68083; Zbl 0909.20051; Zbl 1388.68192; Zbl 1366.68188; Zbl 1401.68212; Zbl 1165.68049; Zbl 1434.68307; Zbl 1407.68314References:
| [1] | J. Adámek, S. Milius, R. Myers, and H. Urbat. Generalized Eilenberg Theorem I: Local Varieties of Languages. In A. Muscholl, editor, {\it Proc. FoSSaCS’14}, volume 8412 of {\it LNCS}, pages 366-380. Springer, 2014. Full version: http://arxiv.org/pdf/1501.02834v1.pdf. · Zbl 1407.68314 |
| [2] | J. Adámek, S. Milius, and H. Urbat. Syntactic monoids in a category. In {\it Proc. CALCO’15}, LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. Full version: http:// arxiv.org/abs/1504.02694. · Zbl 1366.68188 |
| [3] | J. Adámek, R. Myers, S. Milius, and H. Urbat. Varieties of languages in a category. In {\it 30th Annual ACM/IEEE Symposium on Logic in Computer Science}. IEEE, 2015. · Zbl 1401.68212 |
| [4] | J. Almeida. On pseudovarieties, varieties of languages, filters of congruences, pseudoidenti ties and related topics. {\it Algebra Universalis}, 27(3):333-350, 1990. · Zbl 0715.08006 |
| [5] | N. Bedon and O. Carton. An Eilenberg theorem for words on countable ordinals. In {\it Proc.} {\it LATIN’98}, volume 1380 of {\it LNCS}, pages 53-64. Springer, 1998. · Zbl 0906.20045 |
| [6] | N. Bedon and C. Rispal.Schützenberger and Eilenberg theorems for words on linear orderings. In {\it Proc. DLT’05}, volume 3572 of {\it LNCS}, pages 134-145. Springer, 2005. · Zbl 1133.68048 |
| [7] | G. Birkhoff. Rings of sets. {\it Duke Mathematical Journal}, 3(3):443-454, 1937. · Zbl 0017.19403 |
| [8] | M. Bojańczyk. Recognisable languages over monads. In I. Potapov, editor, {\it Proc. DLT’15}, volume 9168 of {\it LNCS}, pages 1-13. Springer, 2015. http://arxiv.org/abs/1502.04898. · Zbl 1434.68307 |
| [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, {\it Proc. FoSSaCS’16}, volume 9634 of {\it LNCS}. Springer, 2016. http://arxiv.org/abs/1511.02147. · Zbl 1474.18010 |
| [10] | L.-T. Chen and H. Urbat. A fibrational approach to automata theory. In L. S. Moss and P. Sobocinski, editors, {\it Proc. CALCO’15}, LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. · Zbl 1366.68190 |
| [11] | L. Daviaud, D. Kuperberg, and J.-É. Pin. Varieties of cost functions. In N. Ollinger and H. Vollmer, editors, {\it Proc. STACS 2016}, volume 47 of {\it LIPIcs}, pages 30:1-30:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016. · Zbl 1388.68192 |
| [12] | S. Eilenberg. {\it Automata, Languages, and Machines Vol. B}. Academic Press, 1976. · Zbl 0359.94067 |
| [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, {\it Proc. CALCO’11}, volume 6859 of {\it LNCS}, pages 192-207. Springer, 2011. · Zbl 1241.68050 |
| [14] | M. Gehrke, S. Grigorieff, and J.-É. Pin. Duality and equational theory of regular languages. In L. Aceto and al., editors, {\it Proc. ICALP’08, Part II}, volume 5126 of {\it LNCS}, pages 246-257. Springer, 2008. · Zbl 1165.68049 |
| [15] | P. T. Johnstone. {\it Stone spaces}. Cambridge University Press, 1982. · Zbl 0499.54001 |
| [16] | E. G. Manes. {\it Algebraic Theories}, volume 26 of {\it Graduate Texts in Mathematics}. Springer, 1976. · Zbl 0353.18007 |
| [17] | G. Matthiessen. Theorie der heterogenen Algebren. Technical report, Universität Bremen, 1976. |
| [18] | G. Matthiessen. A heterogeneous algebraic approach to some problems in automata theory, many-valued logic and other topics. In {\it Proc. Klagenfurt Conf.}, 1979. · Zbl 0402.08008 |
| [19] | D. Perrin and J.-É. Pin. {\it Infinite Words}. Elsevier, 2004. |
| [20] | J.-É. Pin. A variety theorem without complementation. {\it Russ. Math.}, 39:80-90, 1995. |
| [21] | J.-É. Pin. Positive varieties and infinite words. In {\it LATIN 98}, volume 1380 of {\it LNCS}, pages 76-87. Springer, 1998. · Zbl 0909.20051 |
| [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. {\it Th. Comp. Sys.}, 30(2):121-134, 1997. URL: http://link.springer.com/10.1007/BF02679444, doi:10.1007/BF02679444. · Zbl 0870.68092 |
| [24] | L. Polák. Syntactic semiring of a language. In J. Sgall, A. Pultr, and P. Kolman, editors, {\it Proc. MFCS’01}, volume 2136 of {\it LNCS}, pages 611-620. Springer, 2001. · Zbl 1005.68526 |
| [25] | J. Reiterman. The Birkhoff theorem for finite algebras. {\it Algebra Universalis}, 14(1):1-10, 1982. · Zbl 0484.08007 |
| [26] | C. Reutenauer. Séries formelles et algèbres syntactiques. {\it J. Algebra}, 66:448-483, 1980. · Zbl 0444.68075 |
| [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. · Zbl 1224.68056 |
| [29] | S. Salehi and M. Steinby. Tree algebras and varieties of tree languages. {\it Theor. Comput.} {\it Sci.}, 377(1-3):1-24, 2007. · Zbl 1118.68089 |
| [30] | M. P. Schützenberger.On finite monoids having only trivial subgroups.{\it Inform. and} {\it Control}, 8:190-194, 1965. · Zbl 0131.02001 |
| [31] | H. Straubing. On logical descriptions of regular languages. In S. Rajsbaum, editor, {\it LATIN} {\it 2002 Theor. Informatics}, volume 2286 of {\it LNCS}, pages 528-538. Springer, 2002. · Zbl 1059.03034 |
| [32] | D. Thérien. {\it Classification of Regular Languages by Congruences}. PhD thesis, University of Waterloo, 1980. |
| [33] | H. Urbat. A note on HSP theorems. https://www.tu-braunschweig.de/Medien-DB/iti/ hspnote.pdf. · Zbl 1388.68077 |
| [34] | H. Urbat, J. Adámek, L.-T. Chen, and S. Milius. Eilenberg Theorems for Free. https: //arxiv.org/abs/1602.05831. February 2017. · Zbl 1441.68139 |
| [35] | T. Wilke. An Eilenberg theorem for ∞-languages. In {\it Proc. ICALP’91}, volume 510 of {\it LNCS}, pages 588-599. Springer, 1991. · Zbl 0766.68083 |
| [36] | :15 |
| [37] | :15 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
