⊆ ω-words Σ3-complete

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 or equal to] D is a predicate on D. In particular we show: (a) The set of recursive [omega]-words with decidable monadic second order theories is [n-ary summation]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 or equal to] Z, the number of predicates Q [subset of or equal to] 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