A1 Refereed original research article in a scientific journal
Periodicity and unbordered words - A proof of Duval's conjecture
Authors: Harju T, Nowotka D
Publication year: 2004
Journal:: Lecture Notes in Computer Science
Journal name in source: STACS 2004, PROCEEDINGS
Journal acronym: LECT NOTES COMPUT SC
Volume: 2996
First page : 294
Last page: 304
Number of pages: 11
ISBN: 3-540-21236-1
ISSN: 0302-9743
Abstract
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.
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.
UTU Research Portal