Pattern Avoidance

We study pattern avoidance in partial words. The following problems are being investigated:

  1. 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.

  2. 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.