Lyndonwort

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 | Quelltext bearbeiten]

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

  • 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 | Quelltext 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 | Quelltext 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.
  • M. Lothaire: Combinatorics on words. Cambridge University Press, Cambridge 1984, ISBN 0-521-30237-4, (Encyclopedia of mathematics and its applications 17), (englisch).