scientific article; zbMATH DE number 6851884

DOI10.4230/LIPICS.MFCS.2016.51MaRDI QIDQ4608614zbMATH OpenFDO

Authors Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

Publication date 21 March 2018

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2016.51

zbMATH Keywords

avoidabilitypartial stringspartial wordsproof complexityPSPACE-completeness

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Recommendations

• Computational and proof complexity of partial string avoidability
• On the Complexity of Deciding Avoidability of Sets of Partial Words
• On the complexity of deciding avoidability of sets of partial words
• scientific article; zbMATH DE number 6003273
• scientific article; zbMATH DE number 1336330
• On the parameterised complexity of string morphism problems
• On the parameterised complexity of string morphism problems
• String rewriting and proof complexity: an interpretation of resolution
• On the kernelization complexity of string problems
• On the kernelization complexity of string problems

Cited in

(10)

• Testing avoidability on sets of partial words is hard
• The invariant problem for binary string structures and the parallel complexity theory of queries
• Completeness of string analysis for dynamic languages
• scientific article; zbMATH DE number 6003273 (Why is no real title available?)
• On the Complexity of Deciding Avoidability of Sets of Partial Words
• Computational and proof complexity of partial string avoidability
• On the complexity of deciding avoidability of sets of partial words
• Variant Satisfiability of Parameterized Strings
• The string guessing problem as a method to prove lower bounds on the advice complexity
• A complete mechanization of correctness of a string-preprocessing algorithm

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608614)