Computational and Proof Complexity of Partial String Avoidability

DOI10.1145/3442365zbMath1495.68094MaRDI QIDQ5061883

Alexander Okhotin, Dmitry Itsykson, Vsevolod Oparin

Publication date: 14 March 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6463/

zbMATH Keywords

lower bound; 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