一句话：证明字母表大小至少 3 时，子词序结构存在片段可定义的关系恰为递归可枚举关系，并刻画所有量词交替层级。
本文研究有限词 A* 上加入非连续子词序关系后的一阶逻辑 FO，关注各量词交替片段 Σ_i 的表达能力，而非仅可判定性。已知若每个词可作常量，则 Σ_1（存在片段）在二元字母表上已不可判定；但此前对其可定义关系范围了解有限，存在片段的不可判定性证明只表明单字母上的递归可枚举语言及辅助谓词可定义。本文证明：当 |A| ≥ 3 时，带常量 A 上，关系在存在片段中可定义当且仅当它是递归可枚举的。由此得到所有 Σ_i 片段的精确刻画：|A| ≥ 3 时，关系在 Σ_i 中可定义当且仅当它属于算术层级第 i 层。该结果还给出纯逻辑在 i ≥ 2 时的 Σ_i 片段完整描述。
We study first-order logic (FO) over the structure consisting of finite words over some alphabet $A$, together with the (non-contiguous) subword ordering. In terms of decidability of quantifier alternation fragments, this logic is well-understood: If every word is available as a constant, then even the $\Sigma_1$ (i.e., existential) fragment is undecidable, already for binary alphabets $A$. However, up to now, little is known about the expressiveness of the quantifier alternation fragments: For example, the undecidability proof for the existential fragment relies on Diophantine equations and only shows that recursively enumerable languages over a singleton alphabet (and some auxiliary predicates) are definable. We show that if $|A|\ge 3$, then a relation is definable in the existential fragment over $A$ with constants if and only if it is recursively enumerable. This implies characterizations for all fragments $\Sigma_i$: If $|A|\ge 3$, then a relation is definable in $\Sigma_i$ if and only if it belongs to the $i$-th level of the arithmetical hierarchy. In addition, our result yields an analogous complete description of the $\Sigma_i$-fragments for $i\ge 2$ of the pure logic, where the words of $A^*$ are not available as constants.
@article{paperbot2159,
title = {Existential Definability over the Subword Ordering},
author = {Pascal Baumann and Moses Ganardi and Ramanathan S. Thinniyam and Georg Zetzsche},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 4},
year = {2023},
doi = {10.46298/lmcs-19(4:35)2023}
}