A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
About Duval's conjecture
Tekijät: Harju T, Nowotka D
Julkaisuvuosi: 2003
Lehti:: Lecture Notes in Computer Science
Tietokannassa oleva lehden nimi: DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 2710
Aloitussivu: 316
Lopetussivu: 324
Sivujen määrä: 9
ISBN: 3-540-40434-1
ISSN: 0302-9743
Tiivistelmä
A word is called unbordered if it has no proper prefix which is also a suffix of that word. Let mu(w) denote the length of the longest unbordered factor of a word w. Let a word where the longest unbordered prefix equal to mu(w) be called Duval extension. A Duval extension is called trivial, if its longest unbordered factor is of the length of the period of that Duval extension. In 1982 it was shown by Duval that every Duval extension w longer than 3mu(w)-4 is trivial. We improve that bound to 5mu(w)/2-1 in this paper, and with that, move closer to the bound 2mu(w) conjectured by Duval. Our proof also contains a natural application of the Critical Factorization Theorem.
A word is called unbordered if it has no proper prefix which is also a suffix of that word. Let mu(w) denote the length of the longest unbordered factor of a word w. Let a word where the longest unbordered prefix equal to mu(w) be called Duval extension. A Duval extension is called trivial, if its longest unbordered factor is of the length of the period of that Duval extension. In 1982 it was shown by Duval that every Duval extension w longer than 3mu(w)-4 is trivial. We improve that bound to 5mu(w)/2-1 in this paper, and with that, move closer to the bound 2mu(w) conjectured by Duval. Our proof also contains a natural application of the Critical Factorization Theorem.
Turun yliopiston Tutkimustietojärjestelmän portaali