Search Results

Documents authored by Karandikar, Prateek

Document
DOI: 10.4230/LIPIcs.CSL.2016.37
The Height of Piecewise-Testable Languages with Applications in Logical Complexity

Authors: Prateek Karandikar and Philippe Schnoebelen

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract
The height of a piecewise-testable language L is the maximum length of the words needed to define L by excluding and requiring given subwords. The height of L is an important descriptive complexity measure that has not yet been investigated in a systematic way. This paper develops a series of new techniques for bounding the height of finite languages and of languages obtained by taking closures by subwords, superwords and related operations. As an application of these results, we show that FO^2(A^*, subword), the two-variable fragment of the first-order logic of sequences with the subword ordering, can only express piecewise-testable properties and has elementary complexity.
Cite as

Prateek Karandikar and Philippe Schnoebelen. The Height of Piecewise-Testable Languages with Applications in Logical Complexity. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{karandikar_et_al:LIPIcs.CSL.2016.37,
  author =	{Karandikar, Prateek and Schnoebelen, Philippe},
  title =	{{The Height of Piecewise-Testable Languages with Applications in Logical Complexity}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{37:1--37:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.37},
  URN =		{urn:nbn:de:0030-drops-65776},
  doi =		{10.4230/LIPIcs.CSL.2016.37},
  annote =	{Keywords: Descriptive complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.84
Decidability in the Logic of Subsequences and Supersequences

Authors: Prateek Karandikar and Philippe Schnoebelen

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

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 FO^2 theory is decidable while the FO^3 theory is undecidable.
Cite as

Prateek Karandikar and Philippe Schnoebelen. Decidability in the Logic of Subsequences and Supersequences. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 84-97, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{karandikar_et_al:LIPIcs.FSTTCS.2015.84,
  author =	{Karandikar, Prateek and Schnoebelen, Philippe},
  title =	{{Decidability in the Logic of Subsequences and Supersequences}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{84--97},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.84},
  URN =		{urn:nbn:de:0030-drops-56428},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.84},
  annote =	{Keywords: subsequence, subword, logic, first-order logic, decidability, piecewise- testability, Simon’s congruence}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact