City Research Online

Abstract

We prove the undecidability of MSO on ω-words extended with the second-order predicate U1(X) which says that the distance between consecutive positions in a set X⊆N is unbounded. This is achieved by showing that adding U1 to MSO gives a logic with the same expressive power as MSO+U, a logic on ω-words with undecidable satisfiability. As a corollary, we prove that MSO on ω-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.

Publication Type:	Article
Publisher Keywords:	MSO logic, undecidability
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology > Computer Science
SWORD Depositor:	Symplectic Administrator

Export

Downloads