{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T15:15:19Z","timestamp":1770909319059,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,20]],"date-time":"2018-12-20T00:00:00Z","timestamp":1545264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["AD 187\/2-1"],"award-info":[{"award-number":["AD 187\/2-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["MI 717\/5-1"],"award-info":[{"award-number":["MI 717\/5-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>\n            For finite automata as coalgebras in a category\n            <jats:italic>C<\/jats:italic>\n            , we study languages they accept and varieties of such languages. This generalizes Eilenberg\u2019s concept of a variety of languages, which corresponds to choosing as\n            <jats:italic>C<\/jats:italic>\n            the category of Boolean algebras. Eilenberg established a bijective correspondence between pseudovarieties of monoids and varieties of regular languages. In our generalization, we work with a pair\n            <jats:italic>C<\/jats:italic>\n            \/\n            <jats:italic>D<\/jats:italic>\n            of locally finite varieties of algebras that are predual, i.e., dualize on the level of finite algebras, and we prove that pseudovarieties of\n            <jats:italic>D<\/jats:italic>\n            -monoids bijectively correspond to varieties of regular languages in\n            <jats:italic>C<\/jats:italic>\n            . As one instance, Eilenberg\u2019s result is recovered by choosing\n            <jats:italic>D<\/jats:italic>\n            = sets and\n            <jats:italic>C<\/jats:italic>\n            = Boolean algebras. Another instance, Pin\u2019s result on pseudovarieties of ordered monoids, is covered by taking\n            <jats:italic>D<\/jats:italic>\n            = posets and\n            <jats:italic>C<\/jats:italic>\n            = distributive lattices. By choosing as\n            <jats:italic>C<\/jats:italic>\n            amp;equals;\n            <jats:italic>D<\/jats:italic>\n            the self-predual category of join-semilattices, we obtain Pol\u00e1k\u2019s result on pseudovarieties of idempotent semirings. Similarly, using the self-preduality of vector spaces over a finite field\n            <jats:italic>K<\/jats:italic>\n            , our result covers that of Reutenauer on pseudovarieties of\n            <jats:italic>K<\/jats:italic>\n            -algebras. Several new variants of Eilenberg\u2019s theorem arise by taking other predualities, e.g., between the categories of non-unital Boolean rings and of pointed sets. In each of these cases, we also prove a local variant of the bijection, where a fixed alphabet is assumed and one considers local varieties of regular languages over that alphabet in the category\n            <jats:italic>C<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3276771","type":"journal-article","created":{"date-parts":[[2018,12,20]],"date-time":"2018-12-20T13:35:46Z","timestamp":1545312946000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Generalized Eilenberg Theorem"],"prefix":"10.1145","volume":"20","author":[{"given":"Ji\u0159\u00ed","family":"Ad\u00e1mek","sequence":"first","affiliation":[{"name":"Dept. Mathematics, Faculty of Electrical Engineering, Czech Technical University Prague, Prague, Czech Republic"}]},{"given":"Stefan","family":"Milius","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Erlangen, Germany"}]},{"given":"Robert S.R.","family":"Myers","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Braunschweig, Braunschweig, Germany"}]},{"given":"Henning","family":"Urbat","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Erlangen-N\u00fcrnberg, Erlangen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,12,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54830-7_24"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.46"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129506005706"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00378-5"},{"key":"e_1_2_2_5_1","volume-title":"Finite Semigroups and Universal Algebra","author":"Almeida Jorge","unstructured":"Jorge Almeida . 1994. Finite Semigroups and Universal Algebra . World Scientific Publishing , River Edge . Jorge Almeida. 1994. Finite Semigroups and Universal Algebra. World Scientific Publishing, River Edge."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1976-060-2"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-37-00334-X"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21500-6_1"},{"key":"e_1_2_2_9_1","unstructured":"Garrett Brkhoff. 1940. Lattice. Amer. Math. Soc. Providence (Rhode Island).  Garrett Brkhoff. 1940. Lattice. Amer. Math. Soc. Providence (Rhode Island)."},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the 6th Conference on Algebra and Coalgebra in Computer Science (CALCO\u201915)","volume":"35","author":"Chen Liang-Ting","year":"2015","unstructured":"Liang-Ting Chen and Henning Urbat . 2015 . A fibrational approach to automata theory . In Proceedings of the 6th Conference on Algebra and Coalgebra in Computer Science (CALCO\u201915) (LIPIcs), Lawrence S. Moss and Pawel Sobocinski (Eds.) , Vol. 35 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 50--65. Liang-Ting Chen and Henning Urbat. 2015. A fibrational approach to automata theory. In Proceedings of the 6th Conference on Algebra and Coalgebra in Computer Science (CALCO\u201915) (LIPIcs), Lawrence S. Moss and Pawel Sobocinski (Eds.), Vol. 35. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 50--65."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49630-5_31"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53132-7_8"},{"key":"e_1_2_2_13_1","volume-title":"Clark and Brian Davey","author":"David","year":"1998","unstructured":"David M. Clark and Brian Davey . 1998 . Natural Dualities for the Working Algebraist. Cambridge University Press . David M. Clark and Brian Davey. 1998. Natural Dualities for the Working Algebraist. Cambridge University Press."},{"key":"e_1_2_2_14_1","unstructured":"S. Eilenberg. 1976. Automata Languages and Machines Vol. B. Academic Press.   S. Eilenberg. 1976. Automata Languages and Machines Vol. B. Academic Press."},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the International Conference on Algebra and Coalgebra in Computer Science (CALCO\u201911)","volume":"6859","author":"Gabbay M. J.","unstructured":"M. J. Gabbay , T. Litak , and D. Petri\u015fan . 2011. Stone duality for nominal Boolean algebras with new . In Proceedings of the International Conference on Algebra and Coalgebra in Computer Science (CALCO\u201911) (LNCS), A. Corradini, B. Klin, and C. C\u00eerstea (Eds.) , Vol. 6859 . Springer, 192--207. M. J. Gabbay, T. Litak, and D. Petri\u015fan. 2011. Stone duality for nominal Boolean algebras with new. In Proceedings of the International Conference on Algebra and Coalgebra in Computer Science (CALCO\u201911) (LNCS), A. Corradini, B. Klin, and C. C\u00eerstea (Eds.), Vol. 6859. Springer, 192--207."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_21"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2725"},{"key":"e_1_2_2_18_1","volume-title":"Cambridge Studies in Advanced Mathematics","author":"Johnstone Peter T.","unstructured":"Peter T. Johnstone . 1982. Stone Spaces . Cambridge Studies in Advanced Mathematics , Vol. 3 . Cambridge University Press . Peter T. Johnstone. 1982. Stone Spaces. Cambridge Studies in Advanced Mathematics, Vol. 3. Cambridge University Press."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03564-7_17"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.11"},{"key":"e_1_2_2_21_1","first-page":"80","article-title":"A variety theorem without complementation","volume":"39","author":"Pin Jean-\u00c9ric","year":"1995","unstructured":"Jean-\u00c9ric Pin . 1995 . A variety theorem without complementation . Russ. Math. 39 (1995), 80 -- 90 . Jean-\u00c9ric Pin. 1995. A variety theorem without complementation. Russ. Math. 39 (1995), 80--90.","journal-title":"Russ. Math."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679444"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/645730.668038"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/2.2.186"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02483902"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(80)90097-6"},{"key":"e_1_2_2_27_1","volume-title":"The q-theory of Finite Semigroups","author":"Rhodes John","unstructured":"John Rhodes and Benjamin Steinberg . 2008. The q-theory of Finite Semigroups . Springer . John Rhodes and Benjamin Steinberg. 2008. The q-theory of Finite Semigroups. Springer."},{"key":"e_1_2_2_28_1","unstructured":"J. Salam\u00e1nca. February 2017. Unveiling Eilenberg-type Correspondences: Birkhoff\u2019s Theorem for (finite) Algebras + Duality. Retrieved from https:\/\/arxiv.org\/abs\/1702.02822.  J. Salam\u00e1nca. February 2017. Unveiling Eilenberg-type Correspondences: Birkhoff\u2019s Theorem for (finite) Algebras + Duality. Retrieved from https:\/\/arxiv.org\/abs\/1702.02822."},{"key":"e_1_2_2_29_1","unstructured":"H. Urbat. 2017. A note on HSP theorems. Retrieved from https:\/\/www.tu-braunschweig.de\/Medien-DB\/iti\/hspnote.pdf.  H. Urbat. 2017. A note on HSP theorems. Retrieved from https:\/\/www.tu-braunschweig.de\/Medien-DB\/iti\/hspnote.pdf."},{"key":"e_1_2_2_30_1","first-page":"1","article-title":"Eilenberg Theorems for Free. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS'17), Vol. 83","volume":"43","author":"Urbat H.","year":"2017","unstructured":"H. Urbat , J. Ad\u00e1mek , L.-T. Chen , and S. Milius . 2017 . Eilenberg Theorems for Free. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS'17), Vol. 83 . Leibniz International Proceedings in Informatics (LIPIcs) , 43 : 1 -- 43 :15. H. Urbat, J. Ad\u00e1mek, L.-T. Chen, and S. Milius. 2017. Eilenberg Theorems for Free. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS'17), Vol. 83. Leibniz International Proceedings in Informatics (LIPIcs), 43:1--43:15.","journal-title":"Leibniz International Proceedings in Informatics (LIPIcs)"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276771","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3276771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:03:40Z","timestamp":1750273420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276771"}},"subtitle":["Varieties of Languages in a Category"],"short-title":[],"issued":{"date-parts":[[2018,12,20]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3276771"],"URL":"https:\/\/doi.org\/10.1145\/3276771","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,20]]},"assertion":[{"value":"2017-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}