Unavoidable Sets

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◊ma, b◊n1b◊n2b} where a,b are distinct letters in the alphabet and m, n1, n2 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