Unavoidable Sets of Partial Words
F. Blanchet-Sadri, N. C. Brownstein, and Justin Palumbo
The notion of an unavoidable set of words appears frequently in the fields of mathematics and theoretical computer
science, in particular with its connection to the study of combinatorics on words. The theory of
unavoidable sets has seen extensive study over the past twenty years.
In this paper we extend the definition of unavoidable sets of words to unavoidable
sets of partial words. Partial words
, or finite sequences that may contain a number of "do not know" symbols
appear in natural ways in several areas of current interest such as molecular biology, data communication,
DNA computing, etc. We demonstrate the utility of the notion of unavoidability on partial words by making use of
it to identify several new
classes of unavoidable sets of full words. Along the way we begin work on classifying the unavoidable sets of
partial words of small cardinality. We pose a conjecture, and show that affirmative proof of this conjecture gives
a sufficient condition for classifying all of the unavoidable sets of partial words of size two. Lastly we give a result which
makes the conjecture easy to verify for a significant number of cases.
Keywords: Combinatorics on words; unavoidable sets; partial words