2026-07-22T20:50:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5642 2024-03-06T10:36:42Z ddc:004 open_access

Decidability in the Logic of Subsequences and Supersequences Karandikar, Prateek Schnoebelen, Philippe subsequence subword logic first-order logic decidability piecewise- testability Simon’s congruence 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 FO^2 theory is decidable while the FO^3 theory is undecidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prateek Karandikar and Philippe Schnoebelen 2015 Is Part Of LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2015.84 urn:nbn:de:0030-drops-56428 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.84 eng https://creativecommons.org/licenses/by/3.0/legalcode