Infinite and Bi-infinite Words with Decidable Monadic Theories

Dietrich Kuske, Jiamou Liu, Anastasia Moskvina

We study word structures of the form $(D,<,P)$ where $D$ is either $\mathbb{N}$ or $\mathbb{Z}$, $<$ is the natural linear ordering on $D$ and $P\subseteq D$ is a predicate on $D$.…