### Francine Blanchet-Sadri, Brandon Blakeley and Josh Gunter

## Abstract

These papers are related to the following two problems on unavoidable sets: (1) the decision problem of testing the avoidability of finite sets of partial words and (2) the number theoretic problem of classifying two-element unavoidable sets of partial words. Blanchet-Sadri et al. have shown that Problem (1) is NP-hard while Problem (2) reduces to answering a conjecture regarding avoidability of sets of the form {a◊^{m}a, b◊^{n1}b◊^{n2}b} where a,b are distinct letters in the alphabet and m, n_{1}, n_{2} are nonnegative integers. Building on their work, we give in particular a bound on the length of the period of an infinite avoiding word.

*Keywords*: Combinatorics on words; Partial words; Unavoidable sets; NP-hard problems