Reiterman's Theorem on Finite Algebras for a Monad

Adamek J, Chen LT, Milius S, Urbat H (2021)

Publication Type: Journal article

Publication year: 2021

Journal

ACM Transactions on Computational Logic Association for Computing Machinery (ACM)

Book Volume: 22

Journal Issue: 4

DOI: 10.1145/3464691

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 article, Reiterman's theorem is generalized to finite EilenbergMoore algebras for a monad T on a category D: we prove that a class of finite T-algebras is a pseudovariety iff it is presentable by profinite equations. As a key technical tool, we introduce the concept of a profinite monad (T) over cap associated to the monad T, which gives a categorical view of the construction of the space of profinite terms.

Authors with CRIS profile

Stefan Milius Lehrstuhl für Informatik 8 (Theoretische Informatik) Henning Urbat Lehrstuhl für Informatik 8 (Theoretische Informatik)

Involved external institutions

Czech Technical University in Prague / České vysoké učení technické v Praze CZ Czech Republic (CZ) Academia Sinica / 中央研究院 TW Taiwan (TW)

How to cite

APA:

Adamek, J., Chen, L.-T., Milius, S., & Urbat, H. (2021). Reiterman's Theorem on Finite Algebras for a Monad. ACM Transactions on Computational Logic, 22(4). https://doi.org/10.1145/3464691

MLA:

Adamek, Jiri, et al. "Reiterman's Theorem on Finite Algebras for a Monad." ACM Transactions on Computational Logic 22.4 (2021).

BibTeX: Download