Eilenberg Theorems for Free

RISE hosted a talk by Stefan Milius

ABSTRACT

Algebraic language theory studies the behaviour of finite automata of various kinds (e.g., regular languages of finite words, of infinite words, of trees, or their weighted variants) in a machine independent way by relating them to finite algebraic structures. This has proved extremely fruitful. For example, regular languages can be described as the language recognized by finite monoids, and the decidability of star-freeness rests on Schützenberger's theorem: a regular language is star-free iff it is recognized by a finite aperiodic monoid. The backbone of algebraic language theory is formed by more generic correspondences of this kind, called Eilenberg-type correspondences, which relate varieties of languages to pseudovarieties of finite algebras. There exist more than a dozen Eilenberg-type correspondences in the literature today. 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. I will present a variety theorem that covers, besides Eilenberg's classical result, e.g.\ Wilke's and Pin's work on $\infty$-languages, the recent variety theorem for cost functions of Daviaud, Kuperberg, and Pin, and unifies the two categorical approaches of Boja\'nczyk and of Ad\'amek 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.

CONTACT

Laura Kovacs

Stefan Milius, FAU – Friedrich-Alexander-Universität Erlangen-Nürnberg