Generalized Eilenberg theorem. I: Local varieties of languages

DOI10.1007/978-3-642-54830-7_24MaRDI QIDQ5410684zbMATH OpenOpenAlexFDO

Authors Jiří Adámek, Stefan Milius, Robert S. R. Myers, Henning Urbat

Publication date 16 April 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70)

Abstract: We investigate the duality between algebraic and coalgebraic recognition of languages to derive a generalization of the local version of Eilenberg's theorem. This theorem states that the lattice of all boolean algebras of regular languages over an alphabet {Sigma} closed under derivatives is isomorphic to the lattice of all pseudovarieties of {Sigma}-generated monoids. By applying our method to different categories, we obtain three related results: one, due to Gehrke, Grigorieff and Pin, weakens boolean algebras to distributive lattices, one weakens them to join-semilattices, and the last one considers vector spaces over the binary field.

Recommendations

• Generalized Eilenberg theorem. Varieties of languages in a category
• Eilenberg Theorems for Free
• Varieties of Languages in a Category
• Eilenberg's theorem for positive varieties of languages
• Duality and the equational theory of regular languages.

Cited in

(19)

• Measuring power of locally testable languages
• Syntactic structures of regular languages
• Profinite monads, profinite equations, and Reiterman's theorem
• Schützenberger products in a category
• Regular varieties of automata and coequations
• Equations and coequations for weighted automata
• An Eilenberg Theorem for Pictures
• scientific article; zbMATH DE number 3909765 (Why is no real title available?)
• Generalized Eilenberg theorem. Varieties of languages in a category
• A categorical approach to syntactic monoids
• The dual equivalence of equations and coequations for automata
• scientific article; zbMATH DE number 7561623 (Why is no real title available?)
• Eilenberg Theorems for Free
• A fibrational approach to automata theory
• Duality of equations and coequations via contravariant adjunctions
• Measuring power of generalised definite languages
• Semi-Galois categories. I: The classical Eilenberg variety theory
• Carathéodory extensions of subclasses of regular languages
• Coalgebraic constructions of canonical nondeterministic automata

This page was built for publication: Generalized Eilenberg theorem. I: Local varieties of languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5410684)