FINE AND WILF'S THEOREM FOR PARTIAL WORDS WITH ARBITRARILY MANY WEAK PERIODS

摘要

Fine and Wilf's well-known theorem states that any word having periods p, q and length at least p+q - gcd(p, q) also has gcd(p, 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 some "holes." More precisely, any partial word u with H holes having weak periods p, q and length at least the so-denoted l_H(p, q) also has strong 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), 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.