Existential Definability over the Subword Ordering

Abstract

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^{\ast }$ are not available as constants.

References in corpus (2)

• On the index of Simon's congruence for piecewise testability
• General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond