Alexander Okhotin

Computational and Proof Complexity of Partial String Avoidability

2021 · ACM Transactions on Computation Theory

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 …