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 length 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 a positive integer k such that w^k=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.

Keywords: combinatorics on words, Duval's conjecture, Lyndon words, unbordered factors, Sturmian words

Full paper (technical report): [ps - 212 KB] [ps.gz - 101 KB] [pdf - 120 KB].