{"docId":6084,"paperId":5059,"url":"https:\/\/lmcs.episciences.org\/5059","doi":"10.23638\/LMCS-16(1:12)2020","journalName":"Logical Methods in Computer Science","issn":"","eissn":"1860-5974","volume":[{"vid":389,"name":"Volume 16, Issue 1"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"1807.08506","repositoryVersion":5,"repositoryLink":"https:\/\/arxiv.org\/abs\/1807.08506v5","dateSubmitted":"2019-01-02 12:15:58","dateAccepted":"2020-02-11 09:59:44","datePublished":"2020-02-11 10:01:06","titles":["Undecidability of a weak version of MSO+U"],"authors":["Boja\u0144czyk, Miko\u0142aj","Daviaud, Laure","Guillon, Bruno","Penelle, Vincent","Sreejith, A. V."],"abstracts":["We prove the undecidability of MSO on $\\omega$-words extended with the second-order predicate $U_1(X)$ which says that the distance between consecutive positions in a set $X \\subseteq \\mathbb{N}$ is unbounded. This is achieved by showing that adding $U_1$ to MSO gives a logic with the same expressive power as $MSO+U$, a logic on $\\omega$-words with undecidable satisfiability. As a corollary, we prove that MSO on $\\omega$-words becomes undecidable if allowing to quantify over sets of positions that are ultimately periodic, i.e., sets $X$ such that for some positive integer $p$, ultimately either both or none of positions $x$ and $x+p$ belong to $X$."],"keywords":["Computer Science - Logic in Computer Science"]}