Lyndonwort

Ein Lyndonwort ist ein nach Roger Lyndon benanntes formales Wort, das lexikographisch kleiner ist als jede Rotation seiner Buchstaben. Jedes Wort kann eindeutig in eine lexikographisch monoton fallende Folge von Lyndonwörtern zerlegt werden.

Formale Definition

Ein Wort $a$ ist ein Lyndonwort genau dann, wenn für jede Zerlegung $a=uv$ mit nichtleeren Wörtern $u$ und $v$ gilt, dass $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.
• $\mathtt{\text{𝚊𝚊}}$ ist kein Lyndonwort, da mit $u=\mathtt{\text{<mi fromhbox="1">𝚊</mi>}}$ und $v=\mathtt{\text{<mi fromhbox="1">𝚊</mi>}}$ gilt, dass $\mathtt{\text{𝚊𝚊}}=vu$.
• $\mathtt{\text{𝚊𝚋}}$ ist ein Lyndonwort, da $\mathtt{\text{𝚊𝚋}}=uv$ mit $u=\mathtt{\text{<mi fromhbox="1">𝚊</mi>}}$ und $v=\mathtt{\text{<mi fromhbox="1">𝚋</mi>}}$ die einzige Zerlegung in nichtleere Wörter ist und $\mathtt{\text{𝚊𝚋}}<\mathtt{\text{𝚋𝚊}}=vu$ gilt.

Shirshov-Zerlegung

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

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

Weitere Beispiele

• Die Shirshovzerlegung von $\mathtt{\text{𝚊𝚋}}$ ist $\mathtt{\text{𝚊𝚋}}=uv$ mit $u=\mathtt{\text{<mi fromhbox="1">𝚊</mi>}}$ und $v=\mathtt{\text{<mi fromhbox="1">𝚋</mi>}}$.
• Da $\mathtt{\text{𝚊}}<\mathtt{\text{𝚊𝚋}}<\mathtt{\text{𝚋}}$ Lyndonwörter sind, sind auch $\mathtt{\text{𝚊𝚊𝚋}}$ und $\mathtt{\text{𝚊𝚋𝚋}}$ Lyndonwörter.
• Auch $\mathtt{\text{𝚊𝚊𝚋𝚋}}$ ist ein Lyndonwort. Es kann sowohl in die Lyndonwörter $u=\mathtt{\text{<mi fromhbox="1">𝚊</mi>}}$ und $v=\mathtt{\text{𝚊𝚋𝚋}}$ als auch in die Lyndonwörter $u^{\prime }=\mathtt{\text{𝚊𝚊𝚋}}$ und $v^{\prime }=\mathtt{\text{<mi fromhbox="1">𝚋</mi>}}$ zerlegt werden. Da $u$ kürzer ist als $u^{\prime }$, ist $uv$ die Shirshovzerlegung von $\mathtt{\text{𝚊𝚊𝚋𝚋}}$.
• Jedes Lyndonwort hat die Struktur $u^n{v}^m$, wobei $u<v$ Lyndonwörter sind. Auf diese Weise sieht man leicht, dass $\mathtt{\text{𝚊𝚋𝚊𝚋𝚊𝚋𝚋𝚌𝚋𝚌}}$ 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).