Abstract of Paper

The Monadic Theory of Morphic Infinite Words and Generalizations
by Olivier Carton, Wolfgang Thomas

Abstract:

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.