Definitions
Several equivalent definitions are possible.
A k-ary Lyndon word of length n is an n-character string over an alphabet of size k, and which is the minimum element in the lexicographical ordering of all its rotations. Being the singularly smallest rotation implies that a Lyndon word differs from any of its non-trivial rotations, and is therefore aperiodic.
Alternately, a Lyndon word has the property that, whenever it is split into two substrings, the left substring is always lexicographically less than the right substring. That is, if w is a Lyndon word, and w = uv is any factorization into two substrings, with u and v understood to be non-empty, then u < v. This definition implies that w is a Lyndon word if and only if there exist Lyndon words u and v such that u < v and w = uv. Although there may be more than one choice of u and v with this property, there is a particular choice, called the standard factorization, in which v is as long as possible.
Read more about this topic: Lyndon Word
Famous quotes containing the word definitions:
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)
“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (1822–1896)
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)