An Eilenberglike Theorem beyond regular languages
25/05/2018 FCUL  15:30  6.2.53
Célia Borlido (Laboratoire J. A. Dieudonné, CNRS, Université Côte d'Azur)
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 (socalled varieties) and certain classes of finite monoids (socalled 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 nonregular) languages closed under quotients, one can assign a Boolean space equipped with a biaction of a dense monoid (socalled BiM  Boolean space with an internal monoid). While BiMs play the role of profinite monoids in the nonregular 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 Eilenberglike correspondence between varieties of (possibly nonregular) 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:120. [2] M.Gehrke, S.Grigorieff, J.E. Pin. A topological approach to recognition. ICALP 2010: 151162. [3] A.Krebs, K.J. Lange, S.Reifferscheid. Characterizing TC^0 in terms of infinite groups. {STACS} 2005: 496507.
