A1 Refereed original research article in a scientific journal
Periodicity and unbordered words: A proof of the extended Duval conjecture
Authors: Harju T, Nowotka D
Publisher: ASSOC COMPUTING MACHINERY
Publication year: 2007
Journal:: Journal- ACM
Journal name in source: JOURNAL OF THE ACM
Journal acronym: J ACM
Article number: ARTN 20
Volume: 54
Issue: 4
Number of pages: 20
ISSN: 0004-5411
DOI: https://doi.org/10.1145/1255443.1255448
Abstract
The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this article. 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 mu(w) denote the maximum length of all unbordered factors of w, and let partial derivative(w) denote the period of w. Clearly, mu(w) <= partial derivative(w). We establish that mu(w) = partial derivative(w), if w has an unbordered prefix of length mu(w) and n >= 2 mu(w) - 1. This bound is tight and solves the stronger version of an old conjecture by Duval [1983]. It follows from this result that, in general, n >= 3 mu(w) - 3 implies mu(w) = partial derivative(w), which gives an improved bound for the question raised by Ehrenfeucht and Silberger in 1979.
The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this article. 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 mu(w) denote the maximum length of all unbordered factors of w, and let partial derivative(w) denote the period of w. Clearly, mu(w) <= partial derivative(w). We establish that mu(w) = partial derivative(w), if w has an unbordered prefix of length mu(w) and n >= 2 mu(w) - 1. This bound is tight and solves the stronger version of an old conjecture by Duval [1983]. It follows from this result that, in general, n >= 3 mu(w) - 3 implies mu(w) = partial derivative(w), which gives an improved bound for the question raised by Ehrenfeucht and Silberger in 1979.
UTU Research Portal