## Kuske, Dietrich and Liu, Jiamou and Moskvina, Anastasia - Infinite and Bi-infinite Words with Decidable Monadic Theories

lmcs:4140 - Logical Methods in Computer Science, August 21, 2018, Volume 14, Issue 3 - https://doi.org/10.23638/LMCS-14(3:9)2018
Infinite and Bi-infinite Words with Decidable Monadic Theories

Authors: Kuske, Dietrich and Liu, Jiamou and Moskvina, Anastasia

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$. In particular we show: (a) The set of recursive $\omega$-words with decidable monadic second order theories is $\Sigma_3$-complete. (b) Known characterisations of the $\omega$-words with decidable monadic second order theories are transfered to the corresponding question for bi-infinite words. (c) We show that such "tame" predicates $P$ exist in every Turing degree. (d) We determine, for $P\subseteq\mathbb{Z}$, the number of predicates $Q\subseteq\mathbb{Z}$ such that $(\mathbb{Z},\le,P)$ and $(\mathbb{Z},\le,Q)$ are indistinguishable. Through these results we demonstrate similarities and differences between logical properties of infinite and bi-infinite words.

Volume: Volume 14, Issue 3
Published on: August 21, 2018
Submitted on: December 12, 2017
Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory