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.
NSF
Valid CSS!