ABSTRACT
In this chapter, we discuss the fundamental periodicity result on words due to Fine and Wilf in the context of partial words. Fine and Wilf’s result states that any word having periods p and q and length at least p + q − gcd(p, q) has period gcd(p, q). Moreover, the bound p + q − gcd(p, q) is optimal since counterexamples can be provided for words of smaller length. We extend this result to partial words in two ways: First, we discuss weak periodicity extensions, that is, we consider long
enough partial words having weak periods p, q and show that under some conditions they also have period gcd(p, q). We start with partial words with one, two, and three holes, and then generalize the result for partial words with an arbitrary number of holes. The following table describes the number of holes and section numbers where these results are discussed:
0-1 3.1 2-3 3.2
arbitrary 3.3, 3.4 and 3.5
Second, we discuss strong periodicity extensions, that is, we consider in Section 3.6 long enough partial words having strong periods p, q and show that under some conditions they also have period gcd(p, q).
