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

Unbordered Factors and Lyndon Words

Jean-Pierre Duval, Tero Harju, Dirk Nowotka, Unbordered Factors and Lyndon Words . Discrete Mathematics 308, 2261–2264, 2008.

Abstract:

A primitive word w is a Lyndon word if w is minimal among all its conjugates with respect to some lexicographic order.
A word w is bordered if there is a nonempty word u such that
w=uvu for some word v. A right extension of a word w of l
ength n is a word wu where all factors longer than n are bordered.
A right extension wu of w is called trivial if there exists
positive integer k such that wk=uv for some word v.

We prove that Lyndon words have only trivial right extensions.
Moreover, we give a conjecture which characterizes a property
of every word w which has a nontrivial right extension of
length 2|w|-2.

BibTeX entry:

@ARTICLE{jDuHaNo08a,
  title = {Unbordered Factors and Lyndon Words },
  author = {Duval, Jean-Pierre and Harju, Tero and Nowotka, Dirk},
  journal = {Discrete Mathematics},
  volume = {308},
  pages = {2261–2264},
  year = {2008},
  keywords = {Lyndon words, factors, unbordered words, Sturmian words},
}

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

Publication Forum rating of this publication: level 2

Edit publication