mlsanityData to 14 Oct 2026

Decidability in the logic of subsequences and supersequences

arXiv 1510.03994 ↗First posted 14 Oct 2015cs.LO cs.FLcited by 1

Not on the map. Why?

Abstract (arXiv)

We consider first-order logics of sequences ordered by the subsequence ordering, aka sequence embedding. We show that the Sigma2 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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 14 Oct 2015.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Directed Regular and Context-Free Languagescited by 0