Lyndonwort

Ein Lyndonwort i​st ein n​ach Roger Lyndon benanntes formales Wort, d​as lexikographisch kleiner i​st als j​ede Rotation seiner Buchstaben. Jedes Wort k​ann eindeutig i​n eine lexikographisch monoton fallende Folge v​on Lyndonwörtern zerlegt werden.

Formale Definition

Ein Wort ${\displaystyle a}$ ist ein Lyndonwort genau dann, wenn für jede Zerlegung ${\displaystyle a=uv}$ mit nichtleeren Wörtern ${\displaystyle u}$ und ${\displaystyle v}$ gilt, dass ${\displaystyle a<vu}$

Beispiele

• Ein einzelner Buchstabe ist immer ein Lyndonwort, da er nicht in zwei nichtleere Wörter zerlegt werden kann und die Bedingung somit leer ist.
• ${\displaystyle {\texttt {aa}}}$ ist kein Lyndonwort, da mit ${\displaystyle u={\texttt {a}}}$ und ${\displaystyle v={\texttt {a}}}$ gilt, dass ${\displaystyle {\texttt {aa}}=vu}$.
• ${\displaystyle {\texttt {ab}}}$ ist ein Lyndonwort, da ${\displaystyle {\texttt {ab}}=uv}$ mit ${\displaystyle u={\texttt {a}}}$ und ${\displaystyle v={\texttt {b}}}$ die einzige Zerlegung in nichtleere Wörter ist und ${\displaystyle {\texttt {ab}}<{\texttt {ba}}=vu}$ gilt.

Shirshov-Zerlegung

Jedes Lyndonwort, das aus mehr als nur einem Buchstaben besteht, kann in zwei Lyndonwörter ${\displaystyle u}$ und ${\displaystyle v}$ mit ${\displaystyle a=uv}$ und ${\displaystyle u<v}$ zerlegt werden. Die Zerlegung mit kürzestem ${\displaystyle u}$ heißt Shirshov-Zerlegung.

Umgekehrt gilt auch, dass für alle Lyndonwörter ${\displaystyle u}$ und ${\displaystyle v}$ mit ${\displaystyle u<v}$ gilt, dass ${\displaystyle uv}$ ein Lyndonwort ist.

Weitere Beispiele

• Die Shirshovzerlegung von ${\displaystyle {\texttt {ab}}}$ ist ${\displaystyle {\texttt {ab}}=uv}$ mit ${\displaystyle u={\texttt {a}}}$ und ${\displaystyle v={\texttt {b}}}$.
• Da ${\displaystyle {\texttt {a}}<{\texttt {ab}}<{\texttt {b}}}$ Lyndonwörter sind, sind auch ${\displaystyle {\texttt {aab}}}$ und ${\displaystyle {\texttt {abb}}}$ Lyndonwörter.
• Auch ${\displaystyle {\texttt {aabb}}}$ ist ein Lyndonwort. Es kann sowohl in die Lyndonwörter ${\displaystyle u={\texttt {a}}}$ und ${\displaystyle v={\texttt {abb}}}$ als auch in die Lyndonwörter ${\displaystyle u'={\texttt {aab}}}$ und ${\displaystyle v'={\texttt {b}}}$ zerlegt werden. Da ${\displaystyle u}$ kürzer ist als ${\displaystyle u'}$, ist ${\displaystyle uv}$ die Shirshovzerlegung von ${\displaystyle {\texttt {aabb}}}$.
• Jedes Lyndonwort hat die Struktur ${\displaystyle u^{n}v^{m}}$, wobei ${\displaystyle u<v}$ Lyndonwörter sind. Auf diese Weise sieht man leicht, dass ${\displaystyle {\texttt {abababbcbc}}}$ ein Lyndonwort ist.

Literatur

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