# Decidability in the logic of subsequences and supersequences

arXiv: https://arxiv.org/abs/1510.03994 · HTML: https://mlsanity.com/paper/1510.03994/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2015.

## Built on by (most cited first, 1 of 1)

- [Directed Regular and Context-Free Languages](https://mlsanity.com/paper/2401.07106/) (2024)

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