{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:19Z","timestamp":1750220659088,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T00:00:00Z","timestamp":1594166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["683080"],"award-info":[{"award-number":["683080"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,8]]},"DOI":"10.1145\/3373718.3394779","type":"proceedings-article","created":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T00:23:18Z","timestamp":1590452598000},"page":"266-272","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Extensions of \u03c9-Regular Languages"],"prefix":"10.1145","author":[{"given":"Miko\u0142aj","family":"Boja\u0144czyk","sequence":"first","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edon","family":"Kelmendi","sequence":"additional","affiliation":[{"name":"University of Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafa\u0142","family":"Stefa\u0144ski","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Zetzsche","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems (MPI-SWS), Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.277.19"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90148-3"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2108242.2108243"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275227"},{"key":"e_1_3_2_1_5_1","volume-title":"CSL","volume":"3210","author":"Boja\u0144czyk Miko\u0142aj","year":"2004","unstructured":"Miko\u0142aj Boja\u0144czyk . 2004 . A bounding quantifier. In Computer Science Logic , CSL 2004, Karpacz (Lecture Notes in Computer Science), Jerzy Marcinkowski and Andrzej Tarlecki (Eds.) , Vol. 3210 . Springer, 41--55. Miko\u0142aj Boja\u0144czyk. 2004. A bounding quantifier. In Computer Science Logic, CSL 2004, Karpacz (Lecture Notes in Computer Science), Jerzy Marcinkowski and Andrzej Tarlecki (Eds.), Vol. 3210. Springer, 41--55."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9279-2"},{"key":"e_1_3_2_1_7_1","volume-title":"Recognisable languages over monads. CoRR abs\/1502.04898","author":"Boja\u0144czyk Miko\u0142aj","year":"2015","unstructured":"Miko\u0142aj Boja\u0144czyk . 2015. Recognisable languages over monads. CoRR abs\/1502.04898 ( 2015 ). Miko\u0142aj Boja\u0144czyk. 2015. Recognisable languages over monads. CoRR abs\/1502.04898 (2015)."},{"key":"e_1_3_2_1_8_1","unstructured":"Miko\u0142aj Boja\u0144czyk Laure Daviaud Bruno Guillon Vincent Penelle and A. V. Sreejith. (to appear). Undecidability of MSO+\"ultimately Periodic\". Logical Methods in Computer Science abs\/1807.08506 ((to appear)).  Miko\u0142aj Boja\u0144czyk Laure Daviaud Bruno Guillon Vincent Penelle and A. V. Sreejith. (to appear). Undecidability of MSO+\"ultimately Periodic\". Logical Methods in Computer Science abs\/1807.08506 ((to appear))."},{"key":"e_1_3_2_1_9_1","volume-title":"Nicolas Ollinger and Heribert Vollmer (Eds.)","volume":"47","author":"Boja\u0144czyk Miko\u0142aj","year":"2016","unstructured":"Miko\u0142aj Boja\u0144czyk , Pawel Parys , and Szymon Toru\u0144czyk . 2016 . The MSO+U theory of (N, <) is undecidable. In 33rd STACS Orl\u00e9ans, France (LIPIcs) , Nicolas Ollinger and Heribert Vollmer (Eds.) , Vol. 47 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 21:1--21:8. Miko\u0142aj Boja\u0144czyk, Pawel Parys, and Szymon Toru\u0144czyk. 2016. The MSO+U theory of (N, <) is undecidable. In 33rd STACS Orl\u00e9ans, France (LIPIcs), Nicolas Ollinger and Heribert Vollmer (Eds.), Vol. 47. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 21:1--21:8."},{"key":"e_1_3_2_1_10_1","volume-title":"FSTTCS","volume":"4","author":"Boja\u0144czyk Miko\u0142aj","year":"2009","unstructured":"Miko\u0142aj Boja\u0144czyk and Szymon Toru\u0144czyk . 2009 . Deterministic automata and extensions of Weak MSO . In FSTTCS 2009, IIT Kanpur, India (LIPIcs) , Vol. 4 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 73--84. Miko\u0142aj Boja\u0144czyk and Szymon Toru\u0144czyk. 2009. Deterministic automata and extensions of Weak MSO. In FSTTCS 2009, IIT Kanpur, India (LIPIcs), Vol. 4. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 73--84."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"e_1_3_2_1_12_1","volume-title":"Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.)","author":"B\u00fcchi J. Richard","year":"1962","unstructured":"J. Richard B\u00fcchi . 1962 . On a decision method in restricted second order arithmetic. In Logic , Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.) . Stanford Univ. Press, Stanford, Calif., 1--11. J. Richard B\u00fcchi. 1962. On a decision method in restricted second order arithmetic. In Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.). Stanford Univ. Press, Stanford, Calif., 1--11."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3139"},{"key":"e_1_3_2_1_14_1","unstructured":"Samuel Eilenberg. 1974. Automata languages and machines. Vol. A. Academic Press [A subsidiary of Harcourt Brace Jovanovich Publishers] New York.  Samuel Eilenberg. 1974. Automata languages and machines. Vol. A. Academic Press [A subsidiary of Harcourt Brace Jovanovich Publishers] New York."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/2269808"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80018-6"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275466"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2385096.2385101"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_54"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00312-X"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80013-X"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27683-0_19"},{"key":"e_1_3_2_1_24_1","volume-title":"Monadic Second Order Logic with Measure and Category Quantifiers. Logical Methods in Computer Science 14, 2","author":"Mio Matteo","year":"2018","unstructured":"Matteo Mio , Micha\u0142 Skrzypczak , and Henryk Michalewski . 2018. Monadic Second Order Logic with Measure and Category Quantifiers. Logical Methods in Computer Science 14, 2 ( 2018 ). Matteo Mio, Micha\u0142 Skrzypczak, and Henryk Michalewski. 2018. Monadic Second Order Logic with Measure and Category Quantifiers. Logical Methods in Computer Science 14, 2 (2018)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00847-2"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5802\/aif.287"},{"key":"e_1_3_2_1_27_1","series-title":"Pure and applied mathematics series","volume-title":"Infinite words - automata, semigroups, logic and games","author":"Perrin Dominique","unstructured":"Dominique Perrin and Jean-Eric Pin . 2004. Infinite words - automata, semigroups, logic and games . Pure and applied mathematics series , Vol. 141 . Elsevier Morgan Kaufmann . Dominique Perrin and Jean-Eric Pin. 2004. Infinite words - automata, semigroups, logic and games. Pure and applied mathematics series, Vol. 141. Elsevier Morgan Kaufmann."},{"key":"e_1_3_2_1_28_1","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin Michael O.","year":"1969","unstructured":"Michael O. Rabin . 1969 . Decidability of second-order theories and automata on infinite trees . Trans. Amer. Math. Soc. 141 (1969), 1 -- 35 . Michael O. Rabin. 1969. Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141 (1969), 1--35.","journal-title":"Trans. Amer. Math. Soc."},{"volume-title":"Computer Science Logic, Zolt\u00e1n \u00c9sik (Ed.)","author":"Rabinovich Alexander","key":"e_1_3_2_1_29_1","unstructured":"Alexander Rabinovich and Wolfgang Thomas . 2006. Decidable theories of the ordering of natural numbers with unary predicates . In Computer Science Logic, Zolt\u00e1n \u00c9sik (Ed.) . Springer Berlin Heidelberg , Berlin, Heidelberg , 562--574. Alexander Rabinovich and Wolfgang Thomas. 2006. Decidable theories of the ordering of natural numbers with unary predicates. In Computer Science Logic, Zolt\u00e1n \u00c9sik (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 562--574."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1958-0093479-4"},{"key":"e_1_3_2_1_31_1","volume-title":"Mathematical foundations of computer science","author":"Semenov Alexei L.","year":"1984","unstructured":"Alexei L. Semenov . 1984. Decidability of monadic theories . In Mathematical foundations of computer science , 1984 (Prague, 1984). Springer , Berlin, 162--175. Alexei L. Semenov. 1984. Decidability of monadic theories. In Mathematical foundations of computer science, 1984 (Prague, 1984). Springer, Berlin, 162--175."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19710170143"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280812"},{"volume-title":"Handbook of Formal Languages, Volume 3: Beyond Words.","author":"Thomas Wolfgang","key":"e_1_3_2_1_34_1","unstructured":"Wolfgang Thomas . 1997. Languages , automata, and logic . In Handbook of Formal Languages, Volume 3: Beyond Words. , Grzegorz Rozenberg and Arto Salomaa (Eds.). Springer , 389--455. Wolfgang Thomas. 1997. Languages, automata, and logic. In Handbook of Formal Languages, Volume 3: Beyond Words., Grzegorz Rozenberg and Arto Salomaa (Eds.). Springer, 389--455."},{"key":"e_1_3_2_1_35_1","first-page":"326","article-title":"Finite automata and the logic of single-place predicates","volume":"140","author":"Trakhtenbrot Boris A.","year":"1961","unstructured":"Boris A. Trakhtenbrot . 1961 . Finite automata and the logic of single-place predicates . Dokl. Akad. Nauk SSSR 140 , 2 (1961), 326 -- 329 . Boris A. Trakhtenbrot. 1961. Finite automata and the logic of single-place predicates. Dokl. Akad. Nauk SSSR 140, 2 (1961), 326--329.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9694-0"}],"event":{"name":"LICS '20: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"],"location":"Saarbr\u00fccken Germany","acronym":"LICS '20"},"container-title":["Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394779","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373718.3394779","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:35Z","timestamp":1750197755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,8]]},"references-count":36,"alternative-id":["10.1145\/3373718.3394779","10.1145\/3373718"],"URL":"https:\/\/doi.org\/10.1145\/3373718.3394779","relation":{},"subject":[],"published":{"date-parts":[[2020,7,8]]},"assertion":[{"value":"2020-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}