Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture
<|reference_start|>Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture: The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this paper. Consider a finite word w of length n. We call a word bordered, if it has a proper prefix which is also a suffix of that word. Let f(w) denote the maximum length of all unbordered factors of w, and let p(w) denote the period of w. Clearly, f(w) < p(w)+1.   We establish that f(w) = p(w), if w has an unbordered prefix of length f(w) and n > 2f(w)-2. This bound is tight and solves the stronger version of a 21 years old conjecture by Duval. It follows from this result that, in general, n > 3f(w)-3 implies f(w) = p(w) which gives an improved bound for the question asked by Ehrenfeucht and Silberger in 1979.<|reference_end|>
@article{harju2003periodicity,
    title={Periodicity and Unbordered Words: A Proof of the Extended Duval
  Conjecture},
    author={Tero Harju and Dirk Nowotka},
    journal={arXiv preprint arXiv:cs/0305039},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0305039},
    primaryClass={cs.DM}
}