 |
|
|
|
|
 |
In this paper, we give an extension of Fine and Wilf's periodicity result in the context of partial words:
any word with h holes and having a strong period set p and length at least the so-denoted
Lh(p) has also gcd(p) as a strong period. We investigate optimal words for the bound Lh(p),
i.e., partial words u with h holes of length Lh(p) - 1 such that p is a strong period set
of u but gcd(p) is not a strong period of u. We give closed formulas for Lh(p) in a number of cases.
Our approach is based on connectivity in graphs associated with sets of strong periods.
Keywords: Combinatorics on Words; Fine and Wilf's Theorem; Partial Words; Strong Periods; Optimal Lengths.
|
|
|
