Publication:4608614

DOI10.4230/LIPIcs.MFCS.2016.51zbMath1398.68196MaRDI QIDQ4608614

Alexander Okhotin, Dmitry Itsykson, Vsevolod Oparin

Publication date: 21 March 2018

zbMATH Keywords

proof complexity; PSPACE-completeness; avoidability; partial words; partial strings

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R15: Combinatorics on words

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03F20: Complexity of proofs