A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Periodicity and unbordered words - A proof of Duval's conjecture
Tekijät: Harju T, Nowotka D
Julkaisuvuosi: 2004
Lehti:: Lecture Notes in Computer Science
Tietokannassa oleva lehden nimi: STACS 2004, PROCEEDINGS
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 2996
Aloitussivu: 294
Lopetussivu: 304
Sivujen määrä: 11
ISBN: 3-540-21236-1
ISSN: 0302-9743
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali