|Abstract of Paper|
The Monadic Theory of Morphic Infinite Words and Generalizations
by Olivier Carton, Wolfgang Thomas
We present new examples of infinite words which have a decidable monadic theory. Formally, we consider structures $\langle \mathbb N,<,P\rangle$ which expand the ordering $\langle \mathbb N,<\rangle$ of the natural numbers by a unary predicate $P$; the corresponding infinite word is the characteristic 0-1-sequence $x_P$ of $P$. We show that for a morphic predicate $P$ the associated monadic second-order theory MTh$\langle\mathbb N,<,P\rangle$ 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 MTh$\langle\mathbb N,<,P\rangle$ is decidable, which unifies and extends the previously known examples.