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.



Last updated on 14/10/2025 09:44:51 AM