Eilenberg Theorems for Free
From MaRDI portal
Publication:5111258
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 variety theorem that covers e.g. Wilke's and Pin's work on -languages, the 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 we derive a number of new results, including an extension of the local variety theorem of Gehrke, Grigorieff, and Pin from finite to infinite words.
Recommendations
Cites work
- scientific article; zbMATH DE number 2086254 (Why is no real title available?)
- scientific article; zbMATH DE number 1189233 (Why is no real title available?)
- scientific article; zbMATH DE number 1189235 (Why is no real title available?)
- scientific article; zbMATH DE number 3787631 (Why is no real title available?)
- scientific article; zbMATH DE number 176766 (Why is no real title available?)
- scientific article; zbMATH DE number 3549200 (Why is no real title available?)
- scientific article; zbMATH DE number 3561239 (Why is no real title available?)
- scientific article; zbMATH DE number 3623636 (Why is no real title available?)
- scientific article; zbMATH DE number 1848285 (Why is no real title available?)
- A characterisation of NL/poly via nondeterministic finite automata
- A fibrational approach to automata theory
- Developments in Language Theory
- Duality and Equational Theory of Regular Languages
- Eilenberg Theorems for Free
- Generalized Eilenberg theorem. I: Local varieties of languages
- On finite monoids having only trivial subgroups
- On pseudovarieties, varieties of languages, filters of congruences, pseudoidentities and related topics
- Profinite monads, profinite equations, and Reiterman's theorem
- Recognisable languages over monads
- Regular languages and Stone duality
- Rings of sets
- Series formelles et algèbres syntactiques
- Stone Duality for Nominal Boolean Algebras with И
- Syntactic monoids in a category
- The Birkhoff theorem for finite algebras
- Tree algebras and varieties of tree languages
- Varieties of Cost Functions
- Varieties of Languages in a Category
- Varieties of many-sorted recognizable sets
Cited in
(22)- \(\omega\sharp\)-algebras
- On language varieties without Boolean operations
- A fibrational approach to automata theory
- Typed monoids -- an Eilenberg-like theorem for non regular languages
- scientific article; zbMATH DE number 1189235 (Why is no real title available?)
- Generalized Eilenberg theorem. Varieties of languages in a category
- Recognisable languages over monads
- scientific article; zbMATH DE number 7561623 (Why is no real title available?)
- The Power-Set Construction for Tree Algebras
- Eilenberg Theorems for Free
- scientific article; zbMATH DE number 7649885 (Why is no real title available?)
- Generalized Eilenberg theorem. I: Local varieties of languages
- scientific article; zbMATH DE number 7350772 (Why is no real title available?)
- A positive extension of Eilenberg's variety theorem for non-regular languages
- scientific article; zbMATH DE number 176766 (Why is no real title available?)
- Semi-Galois categories. I: The classical Eilenberg variety theory
- Formations of finite monoids and formal languages: Eilenberg's variety theorem revisited.
- Monoidal extended stone duality
- Learning pomset automata
- Regular planar monoidal languages
- Syntactic structures of regular languages
- Profinite monads, profinite equations, and Reiterman's theorem
This page was built for publication: Eilenberg Theorems for Free
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111258)
