Eilenberg Theorems for Free

DOI10.4230/LIPICS.MFCS.2017.43zbMATH Open1441.68139arXiv1602.05831OpenAlexW2963224910MaRDI QIDQ5111258FDOQ5111258

Henning Urbat, Stefan Milius, Liang-Ting Chen, Jiří Adámek

Publication date: 26 May 2020

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 $infty$-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.

Full work available at URL: https://arxiv.org/abs/1602.05831

Recommendations

• Varieties of Languages in a Category
• Generalized Eilenberg theorem. Varieties of languages in a category
• Generalized Eilenberg theorem. I: Local varieties of languages
• Varieties of formal series on trees and Eilenberg's theorem
• scientific article

zbMATH Keywords

dualitymonadvariety of languagespseudovarietyEilenberg's theorem

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70)

Cites Work

• Title not available (Why is that?)
• Rings of sets
• Duality and Equational Theory of Regular Languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• On finite monoids having only trivial subgroups
• Series formelles et algèbres syntactiques
• Regular languages and Stone duality
• Title not available (Why is that?)
• Title not available (Why is that?)
• Developments in Language Theory
• Stone Duality for Nominal Boolean Algebras with И
• The Birkhoff theorem for finite algebras
• Title not available (Why is that?)
• Varieties of Languages in a Category
• Generalized Eilenberg Theorem I: Local Varieties of Languages
• Title not available (Why is that?)
• Tree algebras and varieties of tree languages
• Syntactic Monoids in a Category
• On pseudovarieties, varieties of languages, filters of congruences, pseudoidentities and related topics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Varieties of Cost Functions
• Recognisable Languages over Monads
• Profinite Monads, Profinite Equations, and Reiterman’s Theorem
• Eilenberg Theorems for Free
• A Characterisation of NL/poly via Nondeterministic Finite Automata
• A Fibrational Approach to Automata Theory
• Title not available (Why is that?)

Cited In (14)

• A positive extension of Eilenberg's variety theorem for non-regular languages
• Regular planar monoidal languages
• Title not available (Why is that?)
• Learning pomset automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• On language varieties without Boolean operations
• Syntactic structures of regular languages
• The Power-Set Construction for Tree Algebras
• ω♯-Algebras
• Monoidal extended stone duality
• Title not available (Why is that?)
• Generalized Eilenberg Theorem
• Eilenberg Theorems for Free

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)