Unavoidable Sets of Partial Words of Size Three

by F. Blanchet-Sadri, Andy Kalcic, Tracy Weyand

ABSTRACT

The theory of unavoidable sets has seen extensive study over the past twenty years. Partial words, or finite sequences that may contain a number of "do not know" symbols or holes, appear in natural ways in several areas of current interest such as molecular biology, data communication, DNA computing, etc. In this paper we build on previous work in classifying unavoidable sets with small cardinality by examining unavoidable sets of size three.

Keywords: Combinatorics on words, partial words, unavoidable sets.

Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. DMS-0452020.
Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.