Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650515 | Discrete Mathematics | 2008 | 4 Pages |
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
J.-P. Duval, T. Harju, D. Nowotka,