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
Dirk Nowotka, Tero Harju, About Duval's Conjecture. TUCS Technical Reports 514, Turku Centre for Computer Science, 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:
Full publication in PDF-format
BibTeX entry:
@TECHREPORT{tNoHa03a,
title = {About Duval's Conjecture},
author = {Nowotka, Dirk and Harju, Tero},
number = {514},
series = {TUCS Technical Reports},
publisher = {Turku Centre for Computer Science},
year = {2003},
keywords = {combinatorics on words, Duval's conjecture},
ISBN = {952-12-1136-9},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics