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