Lyndon word

Lyndon word

In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a certain type of string over an alphabet. 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 minimal element in the lexicographical ordering of all its rotations. The minimality implies that a Lyndon word is aperiodic, so differs from any of its non-trivial rotations.

Alternately, a Lyndon word has the property that, whenever it is split into two substrings, it 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 "w" < "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". This property allows the set of all Lyndon words to be generated recursively, whence their importance to computer science.

Lyndon words correspond to aperiodic necklace class representatives and can thus be counted with Moreau's necklace-counting function.

Lyndon words have an application to the description of free Lie algebras, in constructing a basis for the homogeneous part of a given degree. Lyndon words may be understood as a special case of Hall sets.

A theorem of Radford states that the algebra of polynomials of Lyndon words with rational coefficients is a shuffle algebra; that is, they form an algebra over a ring, with multiplication taken to be the shuffle operator.

See also

*De Bruijn sequence

References

*
* Frank Ruskey, " [http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html Info on necklaces, Lyndon words, De Bruijn sequences] ", (2003)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Word problem for groups — In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a recursively presented group G is the algorithmic problem of deciding whether two words represent the same element. Although it… …   Wikipedia

  • Lyndon LaRouche U.S. Presidential campaigns — Lyndon LaRouche s U.S. Presidential campaigns have been a staple of American politics since 1976. LaRouche has run for president on eight consecutive occasions, a record for any candidate, and has tied Harold Stassen s record as a perennial… …   Wikipedia

  • Lyndon LaRouche — Infobox Person name = Lyndon Hermyle LaRouche, Jr. image size = 220px caption = Lyndon LaRouche at a news conference in Paris in February 2006 birth date = birth date and age|1922|9|8 birth place = Rochester, New Hampshire, U.S. death date =… …   Wikipedia

  • Word (group theory) — In group theory, a word is any written product of group elements and their inverses. For example, if x , y , and z are elements of a group G , then xy , z 1 xzz , and y 1 zxx 1 yz 1 are words in the set { x , y , z }. Words play an important role …   Wikipedia

  • Mots de Lyndon — En mathématiques, dans les domaines de la combinatoire et de l informatique, un mot de Lyndon est un certain type de mot sur un alphabet. Il existe différentes définitions équivalentes. Un mot de Lyndon k aire de longueur n est un mot à n lettres …   Wikipédia en Français

  • Views of Lyndon LaRouche — This article is about the views of Lyndon LaRouche. For an overview of his organization, see LaRouche movement, and for the man himself, see Lyndon LaRouche. The views of Lyndon LaRouche cover a wide variety of topics including history, economics …   Wikipedia

  • Neil Lyndon — Residence Fife, Scotland Alma mater Cambridge University Occupation Writer and journalist Years active 1968 to present Employer …   Wikipedia

  • History of the word 'fuck' — In the modern English speaking world, the word fuck is often considered highly offensive. Most English speaking countries censor it on television and radio. A study of the attitudes of the British public found that fuck was considered the third… …   Wikipedia

  • Fernald, Merritt Lyndon — ▪ American botanist born , Oct. 5, 1873, Orono, Maine, U.S. died Sept. 22, 1950, Cambridge, Mass.  American botanist noted for his comprehensive study of the flora of the northeastern United States.       The publication of Fernald s first paper …   Universalium

  • Necklace (combinatorics) — In combinatorics, a k ary necklace of length n is an equivalence class of n character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads of up to k different colors …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”