Abstract: Eilenberg's variety theorem, a centerpiece of algebraic automata theory, establishes a bijective correspondence between varieties of languages and pseudovarieties of monoids. In the present paper this result is generalized to an abstract pair of algebraic categories: we introduce varieties of languages in a category C, and prove that they correspond to pseudovarieties of monoids in a closed monoidal category D, provided that C and D are dual on the level of finite objects. By suitable choices of these categories our result uniformly covers Eilenberg's theorem and three variants due to Pin, Polak and Reutenauer, respectively, and yields new Eilenberg-type correspondences.
Recommendations
- scientific article; zbMATH DE number 1944115
- scientific article; zbMATH DE number 4132134
- Varieties and covarieties of languages (extended abstract)
- Stratified languages
- scientific article; zbMATH DE number 4070361
- scientific article; zbMATH DE number 3483582
- scientific article; zbMATH DE number 3961009
- scientific article; zbMATH DE number 3940746
- scientific article; zbMATH DE number 6606349
- scientific article; zbMATH DE number 2013187
Cited in
(24)- Eilenberg's theorem for positive varieties of languages
- On varieties of ordered automata
- Syntactic structures of regular languages
- A positive extension of Eilenberg's variety theorem for non-regular languages
- Typed monoids -- an Eilenberg-like theorem for non regular languages
- An Eilenberg Theorem for Pictures
- Generalized Eilenberg theorem. Varieties of languages in a category
- Semi-Galois categories. I: The classical Eilenberg variety theory
- A categorical approach to syntactic monoids
- Formations of finite monoids and formal languages: Eilenberg's variety theorem revisited.
- The dual equivalence of equations and coequations for automata
- On varieties of automata enriched with an algebraic structure (extended abstract)
- Quantifiers on languages and codensity monads
- scientific article; zbMATH DE number 7561623 (Why is no real title available?)
- Eilenberg Theorems for Free
- A fibrational approach to automata theory
- Generalized Eilenberg theorem. I: Local varieties of languages
- Literal varieties and pseudovarieties of homomorphisms onto Abelian groups.
- scientific article; zbMATH DE number 6606349 (Why is no real title available?)
- From equational specifications of algebras with structure to varieties of data languages (invited paper)
- Minimisation in logical form
- Context-free languages of string diagrams
- Semi-Galois categories. I: The classical Eilenberg variety theory
- On varieties of meet automata
This page was built for publication: Varieties of Languages in a Category
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635823)
