Paper Info
Title
Infinite and Bi-infinite Words with Decidable Monadic Theories.
Abstract
We study word structures of the form (D, <, P) where D is either N or Z, < is the natural linear ordering on D and P subset of 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) Known characterisations of the omega-words with decidable monadic second order theories are transfered to the corresponding question for bi-infinite words. (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 by monadic second order formulas. Through these results we demonstrate similarities and differences between logical properties of infinite and bi-infinite words.
Year
DOI
Venue
2017
10.23638/LMCS-14(3:9)2018
LOGICAL METHODS IN COMPUTER SCIENCE
DocType
Volume
Issue
Journal
14
3
ISSN
Citations 
PageRank 
1860-5974
0
0.34
References 
Authors
7
3
Name
Order
Citations
PageRank
Dietrich Kuske148547.93
Jiamou Liu24923.19
Anastasia Moskvina300.34