# Existential Definability over the Subword Ordering

arXiv: https://arxiv.org/abs/2210.15642 · HTML: https://mlsanity.com/paper/2210.15642/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2022.

## Built on by (most cited first, 1 of 1)

- [Directed Regular and Context-Free Languages](https://mlsanity.com/paper/2401.07106/) (2024)

## Abstract (arXiv)

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 Sigma1 (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|≥ 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 Sigmai: If |A|≥ 3, then a relation is definable in Sigmai 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 Sigmai-fragments for i≥ 2 of the pure logic, where the words of A^* are not available as constants.