Unavoidable Sets
Abstract   Implementation   Paper (PDF)  

Abstract

Francine Blanchet-Sadri, Sean Simmons and Eric Weissenstein

Partial words are sequences over a finite alphabet that may have undefined positions called holes. In terms of avoidability, sets of partial words serve as efficient representations of large sets of full words. This is strongly analogous to the study of avoidable patterns, in which sets of patterns are used to represent infinite sets of full words. Here, we focus on the following two problems:

(1) the classification of the avoidable sets of partial words of size two over an arbitrary alphabet;
(2) the classification of the patterns avoidable by partial words with infinitely many holes.

Keywords: Combinatorics on words; Partial words; Avoidable sets; Avoidable patterns; Avoidability index; Cayley graphs; Canonical forms.