Semi-Galois categories. I: The classical Eilenberg variety theory

DOI10.1145/2933575.2934528MaRDI QIDQ4635914zbMATH OpenOpenAlexFDO

Authors Takeo Uramoto

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

duality theoremEilenberg's variety theoremprofinite monoidregular languagesemi-Galois category

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Natural dualities for classes of algebras (08C20) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic theory of languages and automata (68Q70)

Abstract: This paper is an extended version of our proceedings paper announced at LICS'16; in order to complement it, this version is written from a different viewpoint including topos-theoretic aspect on our work. Technically, this paper introduces and studies the class of semi-galois categories, which extend galois categories and are dual to profinite monoids in the same way as galois categories are dual to profinite groups; the study on this class of categories is aimed at providing an axiomatic reformulation of Eilenberg's theory of varieties of regular languages--- a branch in formal language theory that has been developed since the mid 1960's and particularly concerns systematic classification of regular languages, finite monoids, and deterministic finite automata. In this paper, detailed proofs of our central results announced at LICS'16 are presented, together with topos-theoretic considerations. The main results include (I) a proof of the duality theorem between profinite monoids and semi-galois categories, extending the duality theorem between profinite groups and galois categories; based on this results on semi-galois categories, we then discuss (II) a reinterpretation of Eilenberg's theory from a viewpoint of duality theorem; in relation with this reinterpretation of the theory, (III) we also give a purely topos-theoretic characterization of classifying topoi BM of profinite monoids M among general coherent topoi, which is a topos-theoretic application of (I). This characterization states that a topos E is equivalent to the classifying topos BM of some profinite monoid M if and only if E is (i) coherent, (ii) noetherian, and (iii) has a surjective coherent point. This topos-theoretic consideration is related to the logical and geometric problems concerning Eilenberg's theory that we addressed at LICS'16, which remain open in this paper.

Recommendations

• Varieties of Languages in a Category
• Generalized Eilenberg theorem. Varieties of languages in a category
• Galois theories of commutative semigroups via semilattices
• Eilenberg Theorems for Free
• scientific article; zbMATH DE number 2125659

Cited in

(9)

• Semi-Galois categories. II: An arithmetic analogue of Christol's theorem
• Galois theory, Hopf algebras, and semiabelian categories. Papers from the workshop on categorical structures for descent and Galois theory, Hopf algebras, and semiabelian categories, Toronto, ON, Canada, September 23--28, 2002
• Ehresmann semigroups whose categories are EI and their representation theory
• Syntactic structures of regular languages
• Schützenberger products in a category
• Monoidal extended stone duality
• Extended Stone duality via monoidal adjunctions
• Semi-galois categories. IV: A deformed reciprocity law for Siegel modular functions
• Semi-Galois categories. I: The classical Eilenberg variety theory

This page was built for publication: Semi-Galois categories. I: The classical Eilenberg variety theory

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