Periodicity properties on partial words

The concept of periodicity has played over the years a central role in the development of combinatorics on words and has been a highly valuable tool for the design and analysis of algorithms. Fine and Wilf’s famous periodicity result, which is one of the most used and known results on words, has extensions to partial words, or sequences that may have a number of “do not know” symbols. These extensions fall into two categories: the ones that relate to strong periodicity and the ones that relate to weak periodicity. In this paper, we obtain consequences by generalizing, in particular, the combinatorial property that “for any word u over {a, b}, ua or ub is primitive,” which proves in some sense that there exist very many primitive partial words.