2026-08-10T12:03:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8103 2024-03-06T10:40:54Z ddc:004 open_access

Eilenberg Theorems for Free Urbat, Henning Adámek, Jiri Chen, Liang-Ting Milius, Stefan Eilenberg's theorem variety of languages pseudovariety monad duality 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henning Urbat and Jiri Adámek and Liang-Ting Chen and Stefan Milius 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.43 urn:nbn:de:0030-drops-81032 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.43 eng https://creativecommons.org/licenses/by/3.0/legalcode