Alladi Ramakrishnan Hall

Decidability in the logic of subsequences and supersequences

Prateek Karandikar

LIAFA, Paris, France

We consider the first-order logic of sequences ordered by the
subsequence ordering, aka sequence embedding. We show that the \Sigma_2
theory is undecidable, answering a question left open by Kuske. Regarding
fragments with a bounded number of variables, we show that the FO2 theory
is decidable while the FO3 theory is undecidable.
This is joint work with Philippe Schnoebelen.