Lyndonwort

A Lyndonwort is by Roger Lyndon named formal word , the lexicographically less than any rotation of its letters. Each word can be clearly broken down into a lexicographically monotonously falling sequence of Lyndon words.

Formal definition

A word is a Lyndon word if and only if for every decomposition with non-empty words and that applies ${\displaystyle a}$ ${\displaystyle a=uv}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle a<vu}$

Examples

• A single letter is always a Lyndon word because it cannot be broken down into two non-empty words and the condition is therefore empty.
• ${\displaystyle {\texttt {aa}}}$is not a Lyndon word, because with and it applies that . ${\displaystyle u={\texttt {a}}}$ ${\displaystyle v={\texttt {a}}}$ ${\displaystyle {\texttt {aa}}=vu}$
• ${\displaystyle {\texttt {ab}}}$is a Lyndon word, since with and the only decomposition into non-empty words is and applies. ${\displaystyle {\texttt {ab}}=uv}$ ${\displaystyle u={\texttt {a}}}$ ${\displaystyle v={\texttt {b}}}$ ${\displaystyle {\texttt {ab}}<{\texttt {ba}}=vu}$

Shirshov decomposition

Any Lyndon word that consists of more than one letter can be split into two Lyndon words and with and . The decomposition with the shortest is called the Shirshov decomposition . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle a=uv}$ ${\displaystyle u<v}$ ${\displaystyle u}$

Conversely, it is also true that for all Lyndon words and with , that is a Lyndon word. ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u<v}$ ${\displaystyle uv}$

Further examples

• The Shirshov decomposition of is with and . ${\displaystyle {\texttt {ab}}}$ ${\displaystyle {\texttt {ab}}=uv}$ ${\displaystyle u={\texttt {a}}}$ ${\displaystyle v={\texttt {b}}}$
• Since Lyndonwörter are also and Lyndonwörter. ${\displaystyle {\texttt {a}}<{\texttt {ab}}<{\texttt {b}}}$ ${\displaystyle {\texttt {aab}}}$ ${\displaystyle {\texttt {abb}}}$
• Also is a Lyndon word. It can be broken down into both the Lyndon words and and the Lyndon words and . Since is shorter than , the Shirshov decomposition of . ${\displaystyle {\texttt {aabb}}}$ ${\displaystyle u={\texttt {a}}}$ ${\displaystyle v={\texttt {abb}}}$ ${\displaystyle u'={\texttt {aab}}}$ ${\displaystyle v'={\texttt {b}}}$ ${\displaystyle u}$ ${\displaystyle u'}$ ${\displaystyle uv}$ ${\displaystyle {\texttt {aabb}}}$
• Each Lyndon word has the structure where Lyndon words are. That way it's easy to see that there is a Lyndon word. ${\displaystyle u^{n}v^{m}}$ ${\displaystyle u<v}$ ${\displaystyle {\texttt {abababbcbc}}}$

literature

• M. Lothaire: Combinatorics on words . Cambridge University Press, Cambridge 1984, ISBN 0-521-30237-4 , ( Encyclopedia of mathematics and its applications 17), (English).