Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alexander Okhotin:

TR20-067 | 30th April 2020
Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

Computational and proof complexity of partial string avoidability

The partial string avoidability problem is stated as follows: given a finite set of strings with possible ``holes'' (wildcard symbols), determine whether there exists a 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 ... more >>>

ISSN 1433-8092 | Imprint