You are here: TUCS > PUBLICATIONS > Publication Search > About Duval's Conjecture
- TUCS Publication Series
- How to Publish in TUCS Series
- Publication Search
- Publication Graph
- Publication Input
- Publication Input Guide
- JuFo Browser
About Duval's Conjecture
Tero Harju, Dirk Nowotka, About Duval's Conjecture. In: Developments in Language Theory (Szeged 2003), Lecture Notes in Computer Science 2710, 316–324, Springer-Verlag, 2003.
Abstract:
<P>A word is called unbordered, if it has no proper prefix
which is also a suffix of that word. Let µ(<i>w</i>)
denote the length of the longest unbordered factor
of a word <i>w</i>. Let a word where the longest unbordered
prefix is equal to µ(<i>w</i>)
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.
<P>In 1982 it was shown by Duval that every Duval extension <i>w</i>
longer than 3µ(<i>w</i>)-4 is trivial. We improve that
bound to 5µ(<i>w</i>)/2-1 in this paper, and with that,
move closer to the bound 2µ(<i>w</i>) conjectured by Duval.
Our proof also contains a natural application of the
Critical Factorization Theorem.
Files:
Abstract in PDF-formatBibTeX entry:
@INPROCEEDINGS{inpHaNo03a,
title = {About Duval's Conjecture},
booktitle = {Developments in Language Theory (Szeged 2003)},
author = {Harju, Tero and Nowotka, Dirk},
volume = {2710},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
pages = {316–324},
year = {2003},
keywords = {combinatorics on words, Duval's conjecture},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics
Publication Forum rating of this publication: level 1