Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering

Simon Halfon, Philippe Schnoebelen, Georg Zetzsche

We consider first-order logic over the subword ordering on finite words, where each word is available as a constant. Our first result is that the ${\Sigma }_1$ theory is undecidable (alrea…