You are here: TUCS > PUBLICATIONS > Publication Search > Periodicity and Unbordered Wor...
- TUCS Publication Series
- How to Publish in TUCS Series
- Publication Search
- Publication Graph
- Publication Input
- Publication Input Guide
- JuFo Browser
Periodicity and Unbordered Words
Tero Harju, Dirk Nowotka, Periodicity and Unbordered Words. TUCS Technical Reports 523, Turku Centre for Computer Science, 2003.
Abstract:
<p>
The relationship between the length of a word and
the maximum length of its unbordered factors
is investigated in this paper.
</p>
<p>
Consider a finite word <i>w</i> of length <i>n</i>.
Let <i>μ</i>(<i>w</i>) denote the maximum length of its
unbordered factors, and let <i>∂</i>(<i>w</i>) denote
the period of <i>w</i>. Clearly,
<i>μ</i>(<i>w</i>) ≤ <i>∂</i>(<i>w</i>).
</p>
<p>
We establish that
<i>μ</i>(<i>w</i>) = <i>∂</i>(<i>w</i>),
if <i>w</i> has an unbordered prefix of length
<i>μ</i>(<i>w</i>) and <i>n</i> ≥ 2<i>μ</i>(<i>w</i>)-1.
This bound is tight and solves a 21 year old conjecture
by Duval. It follows from this result that, in
general, <i>n</i> ≥ 3<i>μ</i>(<i>w</i>) implies
<i>μ</i>(<i>w</i>) = <i>∂</i>(<i>w</i>)
which gives an improved bound for the question
asked by Ehrenfeucht and Silberger in 1979.
</p>
Files:
Full publication in PDF-format
BibTeX entry:
@TECHREPORT{tHaNo03b,
title = {Periodicity and Unbordered Words},
author = {Harju, Tero and Nowotka, Dirk},
number = {523},
series = {TUCS Technical Reports},
publisher = {Turku Centre for Computer Science},
year = {2003},
keywords = {combinatorics on words, periodicity, unbordered factors, Duval's conjecture},
ISBN = {952-12-1154-7},
}
Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics