Periodicity and unbordered words - A proof of Duval's conjecture

: Harju T, Nowotka D

: 2004

Lecture Notes in Computer Science

STACS 2004, PROCEEDINGS

: LECT NOTES COMPUT SC

: 2996

: 294

: 304

: 11

: 3-540-21236-1

: 0302-9743

We establish that mu(w) = partial derivative(w), if w has an unbordered prefix of length mu(w) and n greater than or equal to 2mu(w) - 1. This bound is tight and solves a 21 year old conjecture by Duval. It follows from this result that, in general, n greater than or equal to 3mu(w) implies mu(w) = partial derivative(w) which gives an improved bound for the question asked by Ehrenfeucht and Silberger in 1979.

Mathematics