strong periods in partial words
F. Blanchet-Sadri James Carraher Brian Shirey
Abstract Paper Implementation
Abstract         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.
Partial Words Logo
Valid XHTML 1.0!
Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. DMS-0754154.
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.
Valid CSS!