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.
Done