{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:16:46Z","timestamp":1760080606358,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030992521"},{"type":"electronic","value":"9783030992538"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T00:00:00Z","timestamp":1648512000000},"content-version":"vor","delay-in-days":87,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We show that the existence of a first-order formula separating two monadic second order formulas over countable ordinal words is decidable. This extends the work of Henckell and Almeida on finite words, and of Place and Zeitoun on <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>\u03c9<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-words. For this, we develop the algebraic concept of monoid (resp. <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>\u03c9<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-semigroup, resp. ordinal monoid) with aperiodic merge, an extension of monoids (resp. <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>\u03c9<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-semigroup, resp. ordinal monoid) that explicitly includes a new operation capturing the loss of precision induced by first-order indistinguishability. We also show the computability of FO-pointlike sets, and the decidability of the covering problem for first-order logic on countable ordinal words.<\/jats:p>","DOI":"10.1007\/978-3-030-99253-8_14","type":"book-chapter","created":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T20:02:48Z","timestamp":1648497768000},"page":"264-284","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["First-order separation over countable ordinals"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6529-6963","authenticated-orcid":false,"given":"Thomas","family":"Colcombet","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6360-6363","authenticated-orcid":false,"given":"Sam","family":"van Gool","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1418-3405","authenticated-orcid":false,"given":"R\u00e9mi","family":"Morvan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,29]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Adsul, B., Sarkar, S., Sreejith, A.V.: First-order logic and its infinitary quantifier extensions over countable words (2021)","DOI":"10.1007\/978-3-030-86593-1_3"},{"key":"14_CR2","unstructured":"Almeida, J.: Some algorithmic problems for pseudovarieties. Publ. Math. Debrecen 54(1), 531\u2013552 (1999)"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Almeida, J., Zeitoun, M.: The pseudovariety J is hyperdecidable. RAIRO-Theoretical Informatics and Applications 31(5), 457\u2013482 (1997)","DOI":"10.1051\/ita\/1997310504571"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Ash, C.J.: Inevitable graphs: a proof of the type II conjecture and some related decision procedures. International Journal of Algebra and Computation 1(01), 127\u2013146 (1991)","DOI":"10.1142\/S0218196791000079"},{"key":"14_CR5","doi-asserted-by":"publisher","unstructured":"Bedon, N.: Finite automata and ordinals. Theoretical Computer Science 156(1), 119\u2013144 (1996). https:\/\/doi.org\/10.1016\/0304-3975(95)00006-2","DOI":"10.1016\/0304-3975(95)00006-2"},{"key":"14_CR6","unstructured":"Bedon, N.: Langages reconnaissables de mots index\u00e9s par des ordinaux. Theses, Universit\u00e9 de Marne la Vall\u00e9e (Jan 1998), https:\/\/tel.archives-ouvertes.fr\/tel-00003586"},{"key":"14_CR7","doi-asserted-by":"publisher","unstructured":"Bedon, N.: Logic over words on denumerable ordinals. Journal of Computer and System Sciences 63(3), 394\u2013431 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1782","DOI":"10.1006\/jcss.2001.1782"},{"key":"14_CR8","doi-asserted-by":"publisher","unstructured":"Bedon, N., Carton, O.: An Eilenberg theorem for words on countable ordinals. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN\u201998: Theoretical Informatics. pp. 53\u201364. Springer Berlin Heidelberg, Berlin, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0054310","DOI":"10.1007\/BFb0054310"},{"key":"14_CR9","doi-asserted-by":"publisher","unstructured":"Bedon, N., Rispal, C.: Sch\u00fctzenberger and Eilenberg theorems for words on linear orderings. Journal of Computer and System Sciences 78(2), 517\u2013536 (Mar 2012). https:\/\/doi.org\/10.1016\/j.jcss.2011.06.003","DOI":"10.1016\/j.jcss.2011.06.003"},{"key":"14_CR10","doi-asserted-by":"publisher","unstructured":"B\u00e8s, A., Carton, O.: Algebraic Characterization of FO for Scattered Linear Orderings. In: Bezem, M. (ed.) Computer Science Logic (CSL\u201911) - 25th International Workshop\/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a012, pp. 67\u201381. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2011). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2011.67","DOI":"10.4230\/LIPIcs.CSL.2011.67"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M.: Recognisable languages over monads. In: Potapov, I. (ed.) Developments in Language Theory. pp. 1\u201313. Springer International Publishing, Cham (2015), https:\/\/arxiv.org\/abs\/1502.04898v1","DOI":"10.1007\/978-3-319-21500-6_1"},{"key":"14_CR12","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr .), pp. 1\u201311. Stanford Univ. Press, Stanford, Calif. (1962)"},{"key":"14_CR13","doi-asserted-by":"publisher","unstructured":"B\u00fcchi, J.R.: The monadic second order theory of $$\\omega {_1}$$, pp. 1\u2013127. Springer Berlin Heidelberg (1973). https:\/\/doi.org\/10.1007\/BFb0082721","DOI":"10.1007\/BFb0082721"},{"key":"14_CR14","doi-asserted-by":"publisher","unstructured":"Carton, O., Colcombet, T., Puppis, G.: An algebraic approach to MSO-definability on countable linear orderings (May 2018). https:\/\/doi.org\/10.1017\/jsl.2018.7","DOI":"10.1017\/jsl.2018.7"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Choueka, Y.: Finite automata, definable sets, and regular expressions over $$\\omega $$n-tapes. Journal of Computer and System Sciences 17(1), 81\u201397 (1978)","DOI":"10.1016\/0022-0000(78)90036-3"},{"key":"14_CR16","doi-asserted-by":"publisher","unstructured":"Colcombet, T., Sreejith, A.V.: Limited set quantifiers over countable linear orderings. In: Proceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 9135. pp. 146\u2013158. ICALP 2015, Springer-Verlag, Berlin, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47666-6_12","DOI":"10.1007\/978-3-662-47666-6_12"},{"key":"14_CR17","doi-asserted-by":"publisher","unstructured":"van Gool, S.J., Steinberg, B.: Merge decompositions, two-sided Krohn\u2013Rhodes, and aperiodic pointlikes. Canadian Mathematical Bulletin 62(1), 199\u2013208 (2019). https:\/\/doi.org\/10.4153\/CMB-2018-014-8","DOI":"10.4153\/CMB-2018-014-8"},{"key":"14_CR18","doi-asserted-by":"publisher","unstructured":"Gool, S., Steinberg, B.: Pointlike sets for varieties determined by groups. Advances in Mathematics 348, 18\u201350 (2019). https:\/\/doi.org\/10.1016\/j.aim.2019.03.020","DOI":"10.1016\/j.aim.2019.03.020"},{"key":"14_CR19","doi-asserted-by":"publisher","unstructured":"Henckell, K.: Pointlike sets: the finest aperiodic cover of a finite semigroup. Journal of Pure and Applied Algebra 55(1), 85\u2013126 (1988). https:\/\/doi.org\/10.1016\/0022-4049(88)90042-4","DOI":"10.1016\/0022-4049(88)90042-4"},{"key":"14_CR20","doi-asserted-by":"publisher","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman\u2013Vaught theorem. Annals of Pure and Applied Logic 126(1-3), 159\u2013213 (2004). https:\/\/doi.org\/10.1016\/j.apal.2003.11.002","DOI":"10.1016\/j.apal.2003.11.002"},{"key":"14_CR21","doi-asserted-by":"publisher","unstructured":"Manuel, A., Sreejith, A.V.: Two-variable logic over countable linear orderings. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Krak\u00f3w, Poland. LIPIcs, vol.\u00a058, pp. 66:1\u201366:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.66, https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.66","DOI":"10.4230\/LIPIcs.MFCS.2016.66"},{"key":"14_CR22","unstructured":"McNaughton, R., Papert, S.A.: Counter-Free Automata. The MIT Press (1971)"},{"key":"14_CR23","doi-asserted-by":"publisher","unstructured":"Perrin, D.: Recent results on automata and infinite words. In: International Symposium on Mathematical Foundations of Computer Science. pp. 134\u2013148. Springer (1984). https:\/\/doi.org\/10.1007\/BFb0030294","DOI":"10.1007\/BFb0030294"},{"key":"14_CR24","unstructured":"Pin, J.E., Perrin, D.: Infinite Words: Automata, Semigroups, Logic and Games. Elsevier (2004), https:\/\/hal.archives-ouvertes.fr\/hal-00112831"},{"key":"14_CR25","doi-asserted-by":"publisher","unstructured":"Place, T., Zeitoun, M.: Separating regular languages with first-order logic. Logical Methods in Computer Science 12 (2016). https:\/\/doi.org\/10.2168\/LMCS-12(1:5)2016","DOI":"10.2168\/LMCS-12(1:5)2016"},{"key":"14_CR26","doi-asserted-by":"publisher","unstructured":"Place, T., Zeitoun, M.: The complexity of separation for levels in concatenation hierarchies. In: Ganguly, S., Pandya, P. (eds.) 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0122, pp. 47:1\u201347:17. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2018.47","DOI":"10.4230\/LIPIcs.FSTTCS.2018.47"},{"key":"14_CR27","doi-asserted-by":"publisher","unstructured":"Place, T., Zeitoun, M.: The covering problem. Logical Methods in Computer Science Volume 14, Issue 3 (Jul 2018). https:\/\/doi.org\/10.23638\/LMCS-14(3:1)2018","DOI":"10.23638\/LMCS-14(3:1)2018"},{"key":"14_CR28","unstructured":"Place, T., Zeitoun, M.: On all things star-free. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019), https:\/\/arxiv.org\/abs\/1904.11863v1"},{"key":"14_CR29","doi-asserted-by":"publisher","unstructured":"Place, T., Zeitoun, M.: Separation for dot-depth two. Logical Methods in Computer Science Volume 17, Issue 3 (Sep 2021). https:\/\/doi.org\/10.46298\/lmcs-17(3:24)2021","DOI":"10.46298\/lmcs-17(3:24)2021"},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141, 1\u201335 (1969)","DOI":"10.1090\/S0002-9947-1969-0246760-1"},{"key":"14_CR31","unstructured":"Rispal, C.: Automates sur les ordres lin\u00e9aires : Compl\u00e9mentation. Theses, Universit\u00e9 de Marne la Vall\u00e9e (Dec 2004), https:\/\/tel.archives-ouvertes.fr\/tel-00720658"},{"key":"14_CR32","doi-asserted-by":"crossref","unstructured":"Rispal, C., Carton, O.: Complementation of Rational Sets on Countable Scattered Linear Orderings. International Journal of Foundations of Computer Science 16(4), 767\u2013786 (2005), https:\/\/hal.archives-ouvertes.fr\/hal-00160985","DOI":"10.1142\/S0129054105003285"},{"key":"14_CR33","unstructured":"Rosenstein, J.G.: Linear orderings. Academic press (1982)"},{"key":"14_CR34","doi-asserted-by":"publisher","unstructured":"Sch\u00fctzenberger, M.: On finite monoids having only trivial subgroups. Information and Control 8(2), 190\u2013194 (1965). https:\/\/doi.org\/10.1016\/S0019-9958(65)90108-7","DOI":"10.1016\/S0019-9958(65)90108-7"},{"key":"14_CR35","doi-asserted-by":"crossref","unstructured":"Shelah, S.: The monadic theory of order. Ann. of Math. (2) 102(3), 379\u2013419 (1975)","DOI":"10.2307\/1971037"},{"key":"14_CR36","doi-asserted-by":"crossref","unstructured":"Simon, I.: Piecewise testable events. In: Brakhage, H. (ed.) Automata Theory and Formal Languages. pp. 214\u2013222. Springer Berlin Heidelberg, Berlin, Heidelberg (1975)","DOI":"10.1007\/3-540-07407-4_23"},{"key":"14_CR37","doi-asserted-by":"publisher","unstructured":"Wilke, T.: An algebraic theory for regular languages of finite and infinite words. International Journal of Algebra and Computation 03(04), 447\u2013489 (1993). https:\/\/doi.org\/10.1142\/S0218196793000287","DOI":"10.1142\/S0218196793000287"},{"key":"14_CR38","doi-asserted-by":"publisher","unstructured":"Wilke, T.: Classifying discrete temporal properties. In: Meinel, C., Tison, S. (eds.) STACS 99. pp. 32\u201346. Springer Berlin Heidelberg, Berlin, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-49116-3_3","DOI":"10.1007\/3-540-49116-3_3"},{"key":"14_CR39","doi-asserted-by":"crossref","unstructured":"Wojciechowski, J.: Classes of transfinite sequences accepted by nondeterministic finite automata. Fundamenta informatic\u00e6 7(2), 191\u2013223 (1984)","DOI":"10.3233\/FI-1984-7203"},{"key":"14_CR40","doi-asserted-by":"crossref","unstructured":"Wojciechowski, J.: Finite automata on transfinite sequences and regular expressions. Fundamenta informatic\u00e6 8(3-4), 379\u2013396 (1985)","DOI":"10.3233\/FI-1985-83-407"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-99253-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T20:07:53Z","timestamp":1648498073000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-99253-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030992521","9783030992538"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-99253-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 March 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 April 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 April 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2022\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"77","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}