文章基本信息

标题：Decidability in the Logic of Subsequences and Supersequences
本地全文：下载
作者：Prateek Karandikar ; Philippe Schnoebelen
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：45
页码：84-97
DOI：10.4230/LIPIcs.FSTTCS.2015.84
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：subsequence; subword; logic; first-order logic; decidability; piecewise- testability; Simon's congruence