About Duval’s conjecture
In: http://www.tucs.fi/publications/attachment.php?fname=TR514.pdf, 2003
Online
academicJournal
Zugriff:
A word is called unbordered, if it has no proper prefix which is also a suffix of that word. Let µ(w) denote the length of the longest unbordered factor of a word w. Let a word where the longest unbordered prefix is equal to µ(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 3µ(w)−4 is trivial. We improve that bound to 5µ(w)/2−1 in this paper, and with that, move closer to the bound 2µ(w) conjectured by Duval. Our proof also contains a natural application of the Critical Factorization Theorem. Keywords: combinatorics on words, Duval’s conjecture TUCS Laboratory The periodicity and the borderedness of words are two subjects of basic interest in the study (e.g., Chapter 8 in [10]) and application (e.g., [8]) of combinatorics on words. We investigate the relation between periodicity and
Titel: |
About Duval’s conjecture
|
---|---|
Autor/in / Beteiligte Person: | Harju, Tero ; Nowotka, Dirk ; The Pennsylvania State University CiteSeerX Archives |
Link: | |
Zeitschrift: | http://www.tucs.fi/publications/attachment.php?fname=TR514.pdf, 2003 |
Veröffentlichung: | Springer-Verlag, 2003 |
Medientyp: | academicJournal |
Sonstiges: |
|