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

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

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 >>>