Eilenberg Theorems for Free
From MaRDI portal
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
- 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
- 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?)
- 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
(25)- On language varieties without Boolean operations
- Learning pomset automata
- Syntactic structures of regular languages
- A positive extension of Eilenberg's variety theorem for non-regular languages
- Profinite monads, profinite equations, and Reiterman's theorem
- Typed monoids -- an Eilenberg-like theorem for non regular languages
- Recognisable languages over monads
- scientific article; zbMATH DE number 1189235 (Why is no real title available?)
- scientific article; zbMATH DE number 176766 (Why is no real title available?)
- Generalized Eilenberg theorem. Varieties of languages in a category
- Semi-Galois categories. I: The classical Eilenberg variety theory
- Formations of finite monoids and formal languages: Eilenberg's variety theorem revisited.
- scientific article; zbMATH DE number 7350772 (Why is no real title available?)
- scientific article; zbMATH DE number 7561623 (Why is no real title available?)
- Eilenberg Theorems for Free
- -algebras
- A fibrational approach to automata theory
- Generalized Eilenberg theorem. I: Local varieties of languages
- From equational specifications of algebras with structure to varieties of data languages (invited paper)
- The Power-Set Construction for Tree Algebras
- Regular planar monoidal languages
- Monoidal extended stone duality
- Extended Stone duality via monoidal adjunctions
- Pseudovarieties of semigroups
- Guarded Kleene algebra with tests: coequations, coinduction, and completeness
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)
