Primitive Partial Words.

F. Blanchet-Sadri         Sarah Nelson         Amelia Tebbe

Abstract       Implementation       Paper      

The concept of a word being primitive is useful in many research areas including coding theory, combinatorics on words, formal language theory, and text algorithms. A word is primitive if it cannot be written as a power of another word. The proportion of words that are primitive turns out to be very high. Inspired by a practical problem on gene comparison, Berstel and Boasson introduced in 1999 the notion of a partial word, which is a word that may have some undefined positions, or holes. In this paper, we investigate operations that preserve the primitivity of words and extend them to partial words. As a result, all primitive binary partial words with one hole of length up to 11 can be generated.

Keywords:     Combinatorics on words; partial words; primitive words; primitive partial words