{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T02:46:27Z","timestamp":1776393987028,"version":"3.51.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T00:00:00Z","timestamp":1558569600000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T00:00:00Z","timestamp":1558569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T00:00:00Z","timestamp":1558569600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>We study the strength of axioms needed to prove various results related to automata on infinite words and B\\&amp;quot;uchi's theorem on the decidability of the MSO theory of $(N, {\\le})$. We prove that the following are equivalent over the weak second-order arithmetic theory $RCA_0$:   (1) the induction scheme for $\\Sigma^0_2$ formulae of arithmetic,   (2) a variant of Ramsey's Theorem for pairs restricted to so-called additive colourings,   (3) B\\&amp;quot;uchi's complementation theorem for nondeterministic automata on infinite words,   (4) the decidability of the depth-$n$ fragment of the MSO theory of $(N, {\\le})$, for each $n \\ge 5$.   Moreover, each of (1)-(4) implies McNaughton's determinisation theorem for automata on infinite words, as well as the &amp;quot;bounded-width&amp;quot; version of K\\&amp;quot;onig's Lemma, often used in proofs of McNaughton's theorem.<\/jats:p>","DOI":"10.23638\/lmcs-15(2:16)2019","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T17:38:41Z","timestamp":1743701921000},"source":"Crossref","is-referenced-by-count":2,"title":["The logical strength of B\\\"uchi's decidability theorem"],"prefix":"10.23638","volume":"Volume 15, Issue 2","author":[{"given":"Leszek","family":"Ko\u0142odziejczyk","sequence":"first","affiliation":[]},{"given":"Henryk","family":"Michalewski","sequence":"additional","affiliation":[]},{"given":"C\u00e9cilia","family":"Pradic","sequence":"additional","affiliation":[]},{"given":"Micha\u0142","family":"Skrzypczak","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2019,5,23]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/1608.07514v4","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/1608.07514v4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T17:38:41Z","timestamp":1743701921000},"score":1,"resource":{"primary":{"URL":"http:\/\/lmcs.episciences.org\/4866"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,23]]},"references-count":0,"URL":"https:\/\/doi.org\/10.23638\/lmcs-15(2:16)2019","relation":{"has-preprint":[{"id-type":"arxiv","id":"1608.07514v3","asserted-by":"subject"},{"id-type":"arxiv","id":"1608.07514v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1608.07514","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1608.07514","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,23]]},"article-number":"4866"}}