Existential Definability over the Subword Ordering

Pascal Baumann, Moses Ganardi, Ramanathan S. Thinniyam +1

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…