Periodicity and unbordered words: A proof of the extended Duval conjecture

: Harju T, Nowotka D

Publisher: ASSOC COMPUTING MACHINERY

: 2007

: Journal- ACM

: JOURNAL OF THE ACM

: J ACM

: ARTN 20

: 54

: 4

: 20

: 0004-5411

DOI: https://doi.org/10.1145/1255443.1255448

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.

Mathematics