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$Psubseteq D$ is a predicate on $D$. In particular we show: (a) The set of recursive $omega$-words with decidable monadic second ordertheories is $Sigma_3$-complete. (b) Known characterisations of the $omega$-words with decidable monadicsecond order theories are transfered to the corresponding question forbi-infinite words. (c) We show that such "tame" predicates $P$ exist in every Turing degree. (d) We determine, for $Psubseteqmathbb{Z}$, the number of predicates$Qsubseteqmathbb{Z}$ such that $(mathbb{Z},le,P)$ and $(mathbb{Z},le,Q)$are indistinguishable. Through these results we demonstrate similarities and differences betweenlogical properties of infinite and bi-infinite words.
展开▼
机译：我们研究形式为$（D，<，P）$的词结构，其中$ D $是$ mathbb {N} $或$ mathbb {Z} $，$ <$是$ D $的自然线性排序$ P subseteq D $是$ D $的谓词。特别地，我们显示：（a）具有可确定的一元二阶理论的递归$ omega $词的集合是$ Sigma_3 $ -complete。 （b）将具有可判定的一元二阶理论的$ omega $单词的已知特征转移到相应的双无限单词问题。 （c）我们证明在每个图灵度中都存在这样的“驯服”谓词$ P $。 （d）对于$ P subseteq mathbb {Z} $，我们确定谓词$ Q subseteq mathbb {Z} $的数量，使得$（ mathbb {Z}， le，P）$和$ （ mathbb {Z}， le，Q）$难以区分。通过这些结果，我们证明了无限词和双无限词的逻辑性质之间的异同。
展开▼
