An Eilenberg-like Theorem beyond regular languages

Finite and profinite monoids have proved to be a powerful tool in the study of regular languages. On the one hand, Eilenberg's correspondence, establishing a bijection between certain classes of regular languages (so-called varieties) and certain classes of finite monoids (so-called pseudovarieties), has been used extensively to translate between combinatorial properties of regular languages and algebraic properties of finite monoids. On the other hand, combined with Reiterman's equational theory and augmented by profinite techniques, this correspondence often leads to decidability results - a central issue in Theoretical Computer Science. However, many of the classes of languages of interest to study are not regular, and so, these tools no longer apply. In 2010, Gehrke, Grigorieff and Pin [2] proposed a unified approach to the study of regular languages, using Stone duality. In particular, they realized that profinite monoids could be seen as the extended dual spaces of Boolean algebras of regular languages equipped with a residuation structure. More generally, to a Boolean algebra of (possibly non-regular) languages closed under quotients, one can assign a Boolean space equipped with a biaction of a dense monoid (so-called BiM - Boolean space with an internal monoid). While BiMs play the role of profinite monoids in the non-regular setting, the role of finite monoids is played by typed monoids introduced in [3]. Essentially, a typed monoid is a monoid enriched with a finite Boolean algebra of its powerset. The extra structure is needed since, in general, an infinite monoid will recognize far too many languages. In this talk, after providing the necessary background on Stone duality, I will present an Eilenberg-like correspondence between varieties of (possibly non-regular) languages and pseudovarieties of typed monoids, which generalizes the classical Eilenberg's Theorem. Moreover, in the same way that profinite monoids are projective limits of finite ones, we will see that BiMs can be obtained as a projective limit of certain families of typed monoids.

This is based on joint work with Czarnetzki, Gehrke and Krebs [1].

References: [1] C.Borlido, S.Czarnetzki, M.Gehrke, A.Krebs. Stone duality and the substitution principle. CSL 2017: 13:1-20. [2] M.Gehrke, S.Grigorieff, J.-E. Pin. A topological approach to recognition. ICALP 2010: 151-162. [3] A.Krebs, K.-J. Lange, S.Reifferscheid. Characterizing TC^0 in terms of infinite groups. {STACS} 2005: 496-507.