episciences.org_5059_1670299083
1670299083
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Logical Methods in Computer Science
18605974
02
11
2020
Volume 16, Issue 1
Undecidability of a weak version of MSO+U
Mikołaj
Bojańczyk
Laure
Daviaud
Bruno
Guillon
Vincent
Penelle
A. V.
Sreejith
We prove the undecidability of MSO on $\omega$words extended with the
secondorder 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$.
02
11
2020
5059
https://creativecommons.org/licenses/by/4.0
arXiv:1807.08506
10.48550/arXiv.1807.08506
https://arxiv.org/abs/1807.08506v4
https://arxiv.org/abs/1807.08506v2
10.23638/LMCS16(1:12)2020
https://lmcs.episciences.org/5059

https://lmcs.episciences.org/6084/pdf