Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334739 | Theoretical Computer Science | 2005 | 12 Pages |
Abstract
The well known Fine and Wilf's theorem for words states that if a word has two periods and its length is at least as long as the sum of the two periods minus their greatest common divisor, then the word also has as period the greatest common divisor. We generalise this result for an arbitrary number of periods. Our bound is strictly better in some cases than previous generalisations. Moreover, we prove it optimal. We show also that any extremal word is unique up to letter renaming and give an algorithm to compute both the bound and a corresponding extremal word.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sorin Constantinescu, Lucian Ilie,