Decidability in the logic of subsequences and supersequences
classification
💻 cs.LO
cs.FL
keywords
theoryundecidableansweringboundedconsiderdecidabilitydecidableembedding
read the original abstract
We consider first-order logics 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 paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.