Article ID Journal Published Year Pages File Type
4650515 Discrete Mathematics 2008 4 Pages PDF
Abstract

A primitive word ww is a Lyndon word if ww is minimal among all its conjugates with respect to some lexicographic order. A word ww is bordered if there is a nonempty word u   such that w=uvuw=uvu for some word vv. A right extension of a word ww of length n is a word wu where all factors longer than n are bordered. A right extension wu   of ww is called trivial if there exists a positive integer k   such that wk=uvwk=uv for some word vv.We prove that Lyndon words have only trivial right extensions. Moreover, we give a conjecture which characterizes a property of every word ww which has a nontrivial right extension of length 2|w|-22|w|-2.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,