一句话：研究无限与双向无限字结构的可判定一元二阶理论，给出递归ω-字的复杂度刻画并比较二者异同。
论文研究形式为 (D,<,P) 的字结构，其中 D 为 N 或 Z，< 是自然线性序，P 是子集谓词。核心问题是这些结构的可判定一元二阶（MSO）理论。作者刻画了递归 ω-字中具有可判定 MSO 理论者集合的复杂度，证明其为 Σ_3-完全；将已有 ω-字判定性特征迁移到双向无限字；证明所谓“驯顺”谓词存在于每个图灵度；并对 P⊆Z 确定与 (Z,≤,P) 不可区分的 Q⊆Z 的数量。由此揭示无限字与双向无限字逻辑性质的异同。
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.
@article{paperbot388,
title = {Infinite and Bi-infinite Words with Decidable Monadic Theories},
author = {Dietrich Kuske and Jiamou Liu and Anastasia Moskvina},
journal = {Logical Methods in Computer Science},
volume = {Volume 14, Issue 3},
year = {2018},
doi = {10.23638/lmcs-14(3:9)2018}
}