1 Search Results for "Oparin, Vsevolod"

Document
DOI: 10.4230/LIPIcs.MFCS.2016.51
Computational and Proof Complexity of Partial String Avoidability

Authors: Dmitry Itsykson, Alexander Okhotin, and Vsevolod Oparin

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
The partial string avoidability problem, also known as partial word avoidability, is stated as follows: given a finite set of strings with possible ``holes'' (undefined symbols), determine whether there exists any two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in PSPACE, and this paper establishes its PSPACE-completeness. Next, string avoidability over the binary alphabet is interpreted as a version of conjunctive normal form (CNF) satisfiability problem (SAT), with each clause having infinitely many shifted variants. Non-satisfiability of these formulas can be proved using variants of classical propositional proof systems, augmented with derivation rules for shifting constraints (such as clauses, inequalities, polynomials, etc). Two results on their proof complexity are established. First, there is a particular formula that has a short refutation in Resolution with shift, but requires classical proofs of exponential size (Resolution, Cutting Plane, Polynomial Calculus, etc.). At the same time, exponential lower bounds for shifted versions of classical proof systems are established.
Cite as

Dmitry Itsykson, Alexander Okhotin, and Vsevolod Oparin. Computational and Proof Complexity of Partial String Avoidability. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{itsykson_et_al:LIPIcs.MFCS.2016.51,
  author =	{Itsykson, Dmitry and Okhotin, Alexander and Oparin, Vsevolod},
  title =	{{Computational and Proof Complexity of Partial String Avoidability}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{51:1--51:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.51},
  URN =		{urn:nbn:de:0030-drops-64637},
  doi =		{10.4230/LIPIcs.MFCS.2016.51},
  annote =	{Keywords: partial strings, partial words, avoidability, proof complexity, PSPACE-completeness}
}
  • Refine by Author
  • 1 Itsykson, Dmitry
  • 1 Okhotin, Alexander
  • 1 Oparin, Vsevolod

  • Refine by Classification

  • Refine by Keyword
  • 1 PSPACE-completeness
  • 1 avoidability
  • 1 partial strings
  • 1 partial words
  • 1 proof complexity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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 Imprint Privacy Contact