{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:11Z","timestamp":1750220351439,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T00:00:00Z","timestamp":1631059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grant Agency of the Czech Republic","doi-asserted-by":"crossref","award":["19-00902S"],"award-info":[{"award-number":["19-00902S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["MI 717\/5-2 and SCHR\u00a01118\/8-2"],"award-info":[{"award-number":["MI 717\/5-2 and SCHR\u00a01118\/8-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Research and Training Group 2475 \u201cCybercrime and Forensic Computing\u201d","award":["393541319\/GRK2475\/1-2019"],"award-info":[{"award-number":["393541319\/GRK2475\/1-2019"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            Profinite equations are an indispensable tool for the algebraic classification of formal languages. Reiterman\u2019s theorem states that they precisely specify pseudovarieties, i.e., classes of finite algebras closed under finite products, subalgebras and quotients. In this article, Reiterman\u2019s theorem is generalized to finite Eilenberg-Moore algebras for a monad\u00a0\n            <jats:bold>T<\/jats:bold>\n            on a category\u00a0 D: we prove that a class of finite\n            <jats:bold>T<\/jats:bold>\n            -algebras is a pseudovariety iff it is presentable by profinite equations. As a key technical tool, we introduce the concept of a profinite monad\n            <jats:bold>T<\/jats:bold>\n            <jats:sup>^<\/jats:sup>\n            associated to the monad\n            <jats:bold>T<\/jats:bold>\n            , which gives a categorical view of the construction of the space of profinite terms.\n          <\/jats:p>","DOI":"10.1145\/3464691","type":"journal-article","created":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T19:02:44Z","timestamp":1631127764000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Reiterman\u2019s Theorem on Finite Algebras for a Monad"],"prefix":"10.1145","volume":"22","author":[{"given":"Ji\u0159\u00ed","family":"Ad\u00e1mek","sequence":"first","affiliation":[{"name":"Czech Technical University in Prague, Czech Recublic, and Technische Universit\u00e4t Braunschweig, Germany"}]},{"given":"Liang-Ting","family":"Chen","sequence":"additional","affiliation":[{"name":"Academia Sinica Taiwan, Taipei, Taiwan"}]},{"given":"Stefan","family":"Milius","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Erlangen, Germany"}]},{"given":"Henning","family":"Urbat","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Erlangen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2021,9,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700010704"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/78162"},{"volume-title":"Locally Presentable and Accessible Categories","author":"Ad\u00e1mek Ji\u0159\u00ed","key":"e_1_2_1_3_1","unstructured":"Ji\u0159\u00ed Ad\u00e1mek and Ji\u0159\u00ed Rosick\u00fd . 1994. Locally Presentable and Accessible Categories . Cambridge University Press . 332 pages. Ji\u0159\u00ed Ad\u00e1mek and Ji\u0159\u00ed Rosick\u00fd. 1994. Locally Presentable and Accessible Categories. Cambridge University Press. 332 pages."},{"volume-title":"Algebraic Theories","author":"Ad\u00e1mek Ji\u0159\u00ed","key":"e_1_2_1_4_1","unstructured":"Ji\u0159\u00ed Ad\u00e1mek , Ji\u0159\u00ed Rosick\u00fd , and Enrico Vitale . 2011. Algebraic Theories . Cambridge University Press . Ji\u0159\u00ed Ad\u00e1mek, Ji\u0159\u00ed Rosick\u00fd, and Enrico Vitale. 2011. Algebraic Theories. Cambridge University Press."},{"key":"e_1_2_1_5_1","first-page":"149","article-title":"Subcategories defined by implications","volume":"2","author":"Banaschewski Bernhard","year":"1976","unstructured":"Bernhard Banaschewski and Horst Herrlich . 1976 . Subcategories defined by implications . Houston J. Math. 2 (1976), 149 \u2013 171 . Bernhard Banaschewski and Horst Herrlich. 1976. Subcategories defined by implications. Houston J. Math. 2 (1976), 149\u2013171.","journal-title":"Houston J. Math."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2022278.2022286"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100013463"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-68195-1_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21500-6_1"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 19th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS\u201916)","volume":"547","author":"Chen L.-T.","unstructured":"L.-T. Chen , J. Ad\u00e1mek , S. Milius , and H. Urbat . 2016. Profinite monads, profinite equations and reiterman\u2019s theorem . In Proceedings of the 19th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS\u201916) (Lecture Notes Comput. Sci. , Vol. 9634), B. Jacobs and C. L\u00f6ding (Eds.). Springer, 531\u2013 547 . L.-T. Chen, J. Ad\u00e1mek, S. Milius, and H. Urbat. 2016. Profinite monads, profinite equations and reiterman\u2019s theorem. In Proceedings of the 19th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS\u201916)(Lecture Notes Comput. Sci., Vol. 9634), B. Jacobs and C. L\u00f6ding (Eds.). Springer, 531\u2013547."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/540244"},{"volume-title":"Stone spaces","author":"Johnstone Peter T.","key":"e_1_2_1_12_1","unstructured":"Peter T. Johnstone . 1982. Stone spaces . Cambridge University Press . 398 pages. Peter T. Johnstone. 1982. Stone spaces. Cambridge University Press. 398 pages."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(71)90001-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.10.020"},{"volume-title":"An outline of functorial semantics","author":"Linton F. E. J.","key":"e_1_2_1_16_1","unstructured":"F. E. J. Linton . 1969. An outline of functorial semantics . In Semin. Triples Categ. Homol. Theory, B. Eckmann (Ed.). LNM, Vol . 80. Springer , Berlin, 7\u201352. F. E. J. Linton. 1969. An outline of functorial semantics. In Semin. Triples Categ. Homol. Theory, B. Eckmann (Ed.). LNM, Vol. 80. Springer, Berlin, 7\u201352."},{"volume-title":"Categories for the Working Mathematician (2 ed.)","author":"Lane Saunders Mac","key":"e_1_2_1_17_1","unstructured":"Saunders Mac Lane . 1998. Categories for the Working Mathematician (2 ed.) . Springer . Saunders Mac Lane. 1998. Categories for the Working Mathematician (2 ed.). Springer."},{"volume-title":"Algebraic Theories. Graduate Texts in Mathematics","author":"Manes E. G.","key":"e_1_2_1_18_1","unstructured":"E. G. Manes . 1976. Algebraic Theories. Graduate Texts in Mathematics , Vol. 26 . Springer . E. G. Manes. 1976. Algebraic Theories. Graduate Texts in Mathematics, Vol. 26. Springer."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17127-8_23"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01243597"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-24.3.507"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02483902"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Luis Ribes and Pavel Zalesskii. 2010. Profinite Groups. Springer Berlin.  Luis Ribes and Pavel Zalesskii. 2010. Profinite Groups. Springer Berlin.","DOI":"10.1007\/978-3-642-01642-4"},{"key":"e_1_2_1_24_1","unstructured":"Julian Salamanca. 2017. Unveiling Eilenberg-type Correspondences: Birkhoff\u2019s Theorem for (finite) Algebras + Duality. Retrieved from https:\/\/arxiv.org\/abs\/1702.02822.  Julian Salamanca. 2017. Unveiling Eilenberg-type Correspondences: Birkhoff\u2019s Theorem for (finite) Algebras + Duality. Retrieved from https:\/\/arxiv.org\/abs\/1702.02822."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90108-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700044415"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(72)90019-9"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917)","author":"Urbat Henning","year":"2017","unstructured":"Henning Urbat , Ji\u0159\u00ed Ad\u00e1mek , Liang-Ting Chen , and Stefan Milius . 2017 . Eilenberg theorems for free . In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917) (LIPIcs, Vol. 83), Kim G. Larsen, Hans L . Bodlaender, and Jean-Fran\u00e7ois Raskin (Eds.). Schloss Dagstuhl, 43:1\u201343:14. Retrieved from https:\/\/arxiv.org\/abs\/1602.05831. Henning Urbat, Ji\u0159\u00ed Ad\u00e1mek, Liang-Ting Chen, and Stefan Milius. 2017. Eilenberg theorems for free. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917)(LIPIcs, Vol. 83), Kim G. Larsen, Hans L. Bodlaender, and Jean-Fran\u00e7ois Raskin (Eds.). Schloss Dagstuhl, 43:1\u201343:14. Retrieved from https:\/\/arxiv.org\/abs\/1602.05831."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","volume":"14","author":"Urbat Henning","year":"2019","unstructured":"Henning Urbat and Stefan Milius . 2019 . Varieties of data languages . In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919) (LIPIcs, Vol. 132), Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.). Schloss Dagstuhl, 130:1\u2013130: 14 . Henning Urbat and Stefan Milius. 2019. Varieties of data languages. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)(LIPIcs, Vol. 132), Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.). Schloss Dagstuhl, 130:1\u2013130:14."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3464691","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3464691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:11Z","timestamp":1750191431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3464691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,8]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3464691"],"URL":"https:\/\/doi.org\/10.1145\/3464691","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2021,9,8]]},"assertion":[{"value":"2020-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}