imported>Wheeke: /* Einleitung */

2019-02-01T11:58:23Z

Einleitung

Neue Seite

Ein '''Lyndonwort''' ist ein nach [[Roger Lyndon]] benanntes [[Wort (Theoretische Informatik)|formales Wort]], das [[Lexikographische Ordnung|lexikographisch]] kleiner ist als jede Rotation seiner Buchstaben. Jedes Wort kann eindeutig in eine lexikographisch [[Monotone Abbildung|monoton fallende]] Folge von Lyndonwörtern zerlegt werden.

== Formale Definition ==
Ein Wort <math>a</math> ist ein Lyndonwort genau dann, wenn für jede Zerlegung <math>a = uv</math> mit nichtleeren Wörtern <math>u</math> und <math>v</math> gilt, dass <math>a < vu</math>

== 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.
* <math>\texttt{aa}</math> ist kein Lyndonwort, da mit <math>u=\texttt a</math> und <math>v=\texttt a</math> gilt, dass <math>\texttt{aa} = vu</math>.
* <math>\texttt{ab}</math> ist ein Lyndonwort, da <math>\texttt{ab}=uv</math> mit <math>u=\texttt a</math> und <math>v=\texttt b</math> die einzige Zerlegung in nichtleere Wörter ist und <math>\texttt{ab}<\texttt{ba}=vu</math> gilt.

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

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

== Weitere Beispiele ==
* Die Shirshovzerlegung von <math>\texttt{ab}</math> ist <math>\texttt{ab}=uv</math> mit <math>u=\texttt a</math> und <math>v=\texttt b</math>.
* Da <math>\texttt{a} < \texttt{ab} < \texttt{b}</math> Lyndonwörter sind, sind auch <math>\texttt{aab}</math> und <math>\texttt{abb}</math> Lyndonwörter.
* Auch <math>\texttt{aabb}</math> ist ein Lyndonwort. Es kann sowohl in die Lyndonwörter <math>u=\texttt a</math> und <math>v=\texttt{abb}</math> als auch in die Lyndonwörter <math>u'=\texttt{aab}</math> und <math>v'=\texttt b</math> zerlegt werden. Da <math>u</math> kürzer ist als <math>u'</math>, ist <math>uv</math> die Shirshovzerlegung von <math>\texttt{aabb}</math>.
* Jedes Lyndonwort hat die Struktur <math>u^nv^m</math>, wobei <math>u<v</math> Lyndonwörter sind. Auf diese Weise sieht man leicht, dass <math>\texttt{abababbcbc}</math> 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).

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Algebra]]

Lyndonwort - Versionsgeschichte

imported>Wheeke: /* Einleitung */