Avoidable Patterns in Partial Words
F. Blanchet-Sadri, Kevin Black, and Andrew Zemke
Abstract

A partial word is a sequence of symbols from a finite alphabet that may have some undefined positions, called holes that match every letter of the alphabet. Previously, Blanchet-Sadri, Mercas, Simmons, and Weissenstein completed the classification of binary patterns with respect to partial word avoidability. In this paper, we pose the problem of avoiding patterns in very partial words, that is, partial words very dense with holes. We define the concept of hole sparsity, a measure of the frequency of holes in a partial word. We also present two algorithms that can be used to show that a pattern is avoidable over an alphabet of a given size, allowing for partial words. Finally, we determine the minimum hole sparsity for all unary and some binary patterns in the context of trivial and nontrivial avoidability.