Lyndonwort

ein Wort, das lexikographisch kleiner ist als jede Rotation seiner Buchstaben

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

Bearbeiten

Ein Wort   ist ein Lyndonwort genau dann, wenn für jede Zerlegung   mit nichtleeren Wörtern   und   gilt, dass  

Beispiele

Bearbeiten
  • Ein einzelner Buchstabe ist immer ein Lyndonwort, da er nicht in zwei nichtleere Wörter zerlegt werden kann und die Bedingung somit leer ist.
  •   ist kein Lyndonwort, da mit   und   gilt, dass  .
  •   ist ein Lyndonwort, da   mit   und   die einzige Zerlegung in nichtleere Wörter ist und   gilt.

Shirshov-Zerlegung

Bearbeiten

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

Umgekehrt gilt auch, dass für alle Lyndonwörter   und   mit   gilt, dass   ein Lyndonwort ist.

Weitere Beispiele

Bearbeiten
  • Die Shirshovzerlegung von   ist   mit   und  .
  • Da   Lyndonwörter sind, sind auch   und   Lyndonwörter.
  • Auch   ist ein Lyndonwort. Es kann sowohl in die Lyndonwörter   und   als auch in die Lyndonwörter   und   zerlegt werden. Da   kürzer ist als  , ist   die Shirshovzerlegung von  .
  • Jedes Lyndonwort hat die Struktur  , wobei   Lyndonwörter sind. Auf diese Weise sieht man leicht, dass   ein Lyndonwort ist.

Literatur

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