 |
 |
 |
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
|
Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. DMS-0754154. The Department of Defense is also gratefully acknowledged. |
|
||
|
| Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. |
|