2026-08-17T09:38:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5432 2024-03-06T10:36:27Z ddc:004 open_access

Infinite and Bi-infinite Words with Decidable Monadic Theories Kuske, Dietrich Liu, Jiamou Moskvina, Anastasia infinite words bi-infinite words monadic second order logic We study word structures of the form (D,<=,P) where D is either N or Z, <= is a linear ordering on D and P in D is a predicate on D. In particular we show: (a) The set of recursive omega-words with decidable monadic second order theories is Sigma_3-complete. (b) We characterise those sets P subset of Z that yield bi-infinite words (Z,<=,P) with decidable monadic second order theories. (c) We show that such "tame" predicates P exist in every Turing degree. (d) We determine, for P subset of Z, the number of predicates Q subset of Z such that (Z,<=,P) and (Z,<=,Q) are indistinguishable. Through these results we demonstrate similarities and differences between logical properties of infinite and bi-infinite words. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dietrich Kuske and Jiamou Liu and Anastasia Moskvina 2015 Is Part Of LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2015.472 urn:nbn:de:0030-drops-54325 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.472 eng https://creativecommons.org/licenses/by/3.0/legalcode