• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Duval's Conjecture and Lyndon Words

Tero Harju, Dirk Nowotka, Duval's Conjecture and Lyndon Words. TUCS Technical Reports 479, Turku Centre for Computer Science, 2002.

Abstract:

<p>
Two words <i>w</i> and <i>w'</i> are conjugates if <i>w</i>=<i>xy</i>
and <i>w'</i>=<i>yx</i> for some words <i>x</i> and <i>y</i>.
A word <i>w</i>=<i>u<small>^k</small></i>
is primitive if <i>k</i>=1 for any suitable <i>u</i>.
A primitive word <i>w</i> is a Lyndon word
if <i>w</i> is minimal among all its conjugates
with respect to some lexicographic order.
A word <i>w</i> is bordered if there is a nonempty word <i>u</i>
such that <i>w</i>=<i>uvu</i> for some word <i>v</i>.
A Duval extension of an unbordered word <i>w</i>
of length <i>n</i> is a word <i>wu</i> where all factors
longer than <i>n</i> are bordered.
A Duval extension <i>wu</i> of <i>w</i> is called trivial if
there exists a positive integer <i>k</i> such that
<i>w<small>^k</small></i>=<i>uv</i> for some word <i>v</i>.
</p>
<p>
We prove that Lyndon words have only trivial Duval extensions.
Moreover, we show that every unbordered Sturmian word is
a Lyndon word which extends a result by Mignosi and Zamboni.
We give a conjecture which implies a sharpened
version of Duval's conjecture, namely, that for any word <i>w</i>
of length <i>n</i> any Duval extension longer or equal than 2<i>n</i>-1
is trivial. Our conjecture characterizes a property of every
word <i>w</i> which has a nontrivial Duval extension
of length 2|<i>w</i>|-2.
</p>

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaNo02a,
  title = {Duval's Conjecture and Lyndon Words},
  author = {Harju, Tero and Nowotka, Dirk},
  number = {479},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2002},
  keywords = {combinatorics on words, Duval's conjecture, Lyndon words, Sturmian words},
  ISBN = {952-12-1061-3},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication