Infinite and bi-infinite words with decidable monadic theories

We study word structures of the form (D,<,P) where D is either the naturals or the integers with the natural linear order < and P is a predicate on D. In particular we show: The set of recursive infinite words with decidable monadic second order theories is Sigma_3-complete. We characterise those sets P of integers that yield bi-infinite words with decidable monadic second order theories. We show that such "tame" predicates P exist in every Turing degree. We determine, for a set of integers P, the number of indistinguishable biinfinite words. Through these results we demonstrate similarities and differences between logical properties of infinite and bi-infinite words.