Profinite Monads, Profinite Equations, and Reiterman’s Theorem

DOI10.1007/978-3-662-49630-5_31zbMATH Open1474.18010arXiv1511.02147OpenAlexW2963831834MaRDI QIDQ2811362FDOQ2811362

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

Publication date: 10 June 2016

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

Abstract: Profinite equations are an indispensable tool for the algebraic classification of formal languages. Reiterman's theorem states that they precisely specify pseudovarieties, i.e. classes of finite algebras closed under finite products, subalgebras and quotients. In this paper Reiterman's theorem is generalised to finite Eilenberg-Moore algebras for a monad T on a variety D of (ordered) algebras: a class of finite T-algebras is a pseudovariety iff it is presentable by profinite (in-)equations. As an application, quasivarieties of finite algebras are shown to be presentable by profinite implications. Other examples include finite ordered algebras, finite categories, finite infinity-monoids, etc.

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

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Monads (= standard construction, triple or triad), algebras for monads, homology and derived functors for monads (18C15) Products, amalgamated products, and other kinds of limits and colimits (08B25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Varieties of ordered algebras
• Duality and Equational Theory of Regular Languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ordered Topological Spaces and the Representation of Distributive Lattices
• Profinite Groups
• On finite monoids having only trivial subgroups
• Series formelles et algèbres syntactiques
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Birkhoff theorem for finite algebras
• Generalized Eilenberg Theorem I: Local Varieties of Languages
• Coalgebraic constructions of canonical nondeterministic automata
• Profinite categories, implicit operations and pseudovarieties of categories
• Syntactic Monoids in a Category
• The Birkhoff theorem for varieties of finite algebras
• On pseudovarieties, varieties of languages, filters of congruences, pseudoidentities and related topics
• Title not available (Why is that?)
• A Reiterman theorem for pseudovarieties of finite first-order structures
• Equational completion, model induced triples and pro-objects
• Recognisable Languages over Monads
• Title not available (Why is that?)
• A Fibrational Approach to Automata Theory

Cited In (13)

• A Reiterman theorem for pseudovarieties of finite first-order structures
• Reiterman’s Theorem on Finite Algebras for a Monad
• Quantifiers on languages and codensity monads
• On language varieties without Boolean operations
• Syntactic structures of regular languages
• Eilenberg's variety theorem without Boolean operations
• Title not available (Why is that?)
• Generalized Eilenberg Theorem
• Whither semantics?
• Codensity, profiniteness and algebras of semiring-valued measures
• Eilenberg Theorems for Free
• Schützenberger Products in a Category
• Title not available (Why is that?)

This page was built for publication: Profinite Monads, Profinite Equations, and Reiterman’s Theorem

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