Computing Weak Periods of Partial Words

by F. Blanchet-Sadri, Taktin Oey, Tim Rankin

Paper Implementation


Fine and Wilf's well-known theorem states that any word having periods p and q and length at least p+q-gcd(p,q) also has gcd(p,q), the greatest common divisor of p and q, as a period. Moreover, the length p+q-gcd(p,q) is critical since counterexamples can be provided for shorter words. This result has since been extended to partial words, or finite sequences that may contain a number of "do not know" symbols or "holes." More precisely, any partial word u with H holes having weak periods p, q and length at least the so-denoted lH(p,q) also has period gcd(p,q) provided u is not (H,(p,q))-special. This extension was done for one hole by Berstel and Boasson (where the class of (1,(p,q)-special partial words is empty), for two or three holes by Blanchet-Sadri and Hegstrom, and for an arbitrary number of holes by Blanchet-Sadri. In this paper, we further extend these results, allowing an arbitrary number of weak periods. In addition to speciality, the concepts of intractable period sets and interference between periods play a role.

Keywords: Word, Partial Word, Period, Weak Period, Critical Length, Special, Interference, Intractable.

Visit the NSF home page.
Valid XHTML 1.0!

Acknowledgement:   This material is based upon work supported by the National Science Foundation under Grant No. DMS-0452020.
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.

Site background from

Valid CSS!