Eilenberg Theorems for Free

ABSTRACT. Algebraic language theory investigates the behaviors of finite machines by relating them to finite algebraic structures. For instance, regular languages - the behaviours of finite automata - can be described purely algebraically as the languages recognized by finite monoids, and a fundamental relation between these concepts is given by Eilenberg’s variety theorem: varieties of languages (classes of regular languages closed under boolean operations, derivatives, and preimages of monoid morphisms) correspond bijectively to pseudovarieties of monoids (classes of finite monoids closed under homomorphic images, submonoids, and finite products). This together with Reiterman's theorem, which characterizes pseudovarieties as the classes of monoids presentable by profinite equations, establishes a firm connection between automata, algebra, topology, and logic. Dozens of extensions of these results are known which consider either notions of varieties with modified closure properties, or other types languages such as omega-regular languages, tree languages or cost functions. In this talk, I will outline a uniform category theoretic approach to algebraic language theory that encompasses all the above work. The key idea is to (1) model languages and the algebraic structures recognizing them by a monad T on some algebraic category D; (2) interpret profinite equations and Reiterman’s theorem by means of a codensity monad induced by T, called the profinite monad; and (3) interpret the algebraic recognition of languages in terms of second algebraic category C that dualizes to D on the level of finite algebras. As a result, we obtain an Eilenberg-Reiterman correspondence which establishes a bijective correspondence between varieties of T-recognizable languages, pseudovarieties of T-algebras, and profinite equational theories. The classical case of regular languages is recovered by taking the categories C = boolean algebras and D = sets, and the free-monoid monad on D. Likewise, by varying the parameters, almost all Eilenberg-Reiterman correspondences known in the literature emerge as special cases of the categorical framework. In addition, a number of new results come for free, including a variety theorem for data languages. The presentation is based on the recent paper: H. Urbat, J. Adámek, L. -T. Chen, S. Milius: Eilenberg Theorems for Free. Proc. 42nd International Symposium on Mathematical Foundations of Computer Science (2017). EATCS Best Paper Award. LIPIcs, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

Authors

• Henning Urbat

Keywords

No keywords are indexed for this paper.