• Media type: E-Article
  • Title: Reiterman’s Theorem on Finite Algebras for a Monad
  • Contributor: Adámek, Jiří; Chen, Liang-Ting; Milius, Stefan; Urbat, Henning
  • imprint: Association for Computing Machinery (ACM), 2021
  • Published in: ACM Transactions on Computational Logic
  • Language: English
  • DOI: 10.1145/3464691
  • ISSN: 1529-3785; 1557-945X
  • Keywords: Computational Mathematics ; Logic ; General Computer Science ; Theoretical Computer Science
  • Origination:
  • Footnote:
  • Description: <jats:p> 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 Eilenberg-Moore algebras for a monad  <jats:bold>T</jats:bold> on a category  D: we prove that a class of finite <jats:bold>T</jats:bold> -algebras is a pseudovariety iff it is presentable by profinite equations. As a key technical tool, we introduce the concept of a profinite monad <jats:bold>T</jats:bold> <jats:sup>^</jats:sup> associated to the monad <jats:bold>T</jats:bold> , which gives a categorical view of the construction of the space of profinite terms. </jats:p>
  • Access State: Open Access