Talk "One Eilenberg Theorem to Rule Them All"

by Stefan Milius

Wed, 11 January 2017 at 02:00 pm in Binz (Rügen), Germany

Joint work with: Jiri Adamek, Liang-Ting Chen, Henning Urbat

Abstract: 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. Numerous such correspondences are known in the literature. We demonstrate 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 generic variety theorem that covers more than a dozen Eilenberg-type correspondences in the literature, among them e.g. Wilke's and Pin's work on $\infty$-languages as well as the recent variety theorem for cost functions of Daviaud, Kuperberg, and Pin, and unifies the two previous categorical approaches of Boja\'nczyk and of Ad\'amek et al. In addition it gives a number of new results, such as an extension of the local variety theorem of Gehrke, Grigorieff, and Pin from finite to infinite words.