We study pattern avoidance in partial words. The following problems are being investigated:
-
The avoidability index of a pattern p is the smallest integer k such that there exists an infinite word on k letters that avoids p. The classification of the avoidability indices of unary and binary patters are known. The classification for ternary patterns is almost complete.
-
The minimum hole sparsity of a pattern p is the smallest integer λ such that there exists an infinite word that avoids p and has at least one hole in every factor of length λ. The classification of minimum hole sparsities for unary patterns is known. The classification for binary patterns over a binary alphabet is in progress.
Keywords: Combinatorics on words; Pattern avoidance; Partial words; Avoidability index; Minimum hole sparsity.
