@Unpublished{     city21301,
  Author        = "Boja{\'n}czyk, M. and Daviaud, L. and Guillon, B. and Penelle, V. and Sreejith, A.V.",
  Abstract      = "We prove the undecidability of mso on {\ensuremath{\omega}} -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 {\ensuremath{\omega}} -words with undecidable satisfiability. As a corollary, we prove that mso on {\ensuremath{\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",
  date-added    = "2019-02-05 14:26:21 +0100",
  date-modified = "2019-02-05 14:26:21 +0100",
  Note          = "This is a preprint article that has been submitted to Logic Methods in Computer Science.",
  Title         = "Undecidability of a weak version of MSO+U",
  Type          = "Working Paper",
  URL           = "http://openaccess.city.ac.uk/21301/",
  bdsk-url-1    = "http://openaccess.city.ac.uk/21301/",
  File          = "1807.08506v2 (0) - a - a - q.pdf",
  file-2        = "Undecidability of a weak version of MSO+U - 1807.08506 - a - a - a - q.pdf"
}

@Unpublished{ city21301, Author = "Boja{\'n}czyk, M. and Daviaud, L. and Guillon, B. and Penelle, V. and Sreejith, A.V.", Abstract = "We prove the undecidability of mso on {\ensuremath{\omega}} -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 {\ensuremath{\omega}} -words with undecidable satisfiability. As a corollary, we prove that mso on {\ensuremath{\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", date-added = "2019-02-05 14:26:21 +0100", date-modified = "2019-02-05 14:26:21 +0100", Note = "This is a preprint article that has been submitted to Logic Methods in Computer Science.", Title = "Undecidability of a weak version of MSO+U", Type = "Working Paper", URL = "http://openaccess.city.ac.uk/21301/", bdsk-url-1 = "http://openaccess.city.ac.uk/21301/", File = "1807.08506v2 (0) - a - a - q.pdf", file-2 = "Undecidability of a weak version of MSO+U - 1807.08506 - a - a - a - q.pdf" }