The Monadic Theory of Morphic Infinite Words and Generalizations

We present new examples of infinite words which have a decidable monadic theory. Formally, we consider structures hN; <; P i which expand the ordering hN; <i of the natural numbers by a unary predicate P ; the corresponding infinite word is the characteristic 0-1-sequence xP of P . We show that for a morphic predicate P the associated monadic second-order theory MThhN; <; P i is decidable, thus extending results of Elgot and Rabin (1966) and Maes (1999). The solution is obtained in the framework of semigroup theory, which is then connected to the known automata theoretic approach of Elgot and Rabin. Finally, a large class of predicates P is exhibited such that the monadic theory MThhN; <; P i is decidable, which unifies and extends the previously known examples.