Kombinatorik auf Wörtern

Gegenstand und Grundbegriffe

Die Kombinatorik auf Wörtern ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Sie untersucht die Struktur und Eigenschaften von Wörtern einer Gruppe, zum Beispiel von Wörtern einer formalen Sprache. Verbindungen bestehen unter anderem zur Algebra, Wahrscheinlichkeitstheorie, Zahlentheorie, Logik, symbolischen Dynamik, Komplexitätstheorie, Berechenbarkeitstheorie und Automatentheorie. Anwendungen gibt es auch in Physik und Biologie.

Ein Alphabet ist eine endliche Menge, deren Elemente Buchstaben heißen. Ein Wort ist eine endliche oder unendliche Folge von Buchstaben eines Alphabets. Die kleenesche Hülle A* ist die Menge aller endlichen Wörter, die aus dem Alphabet A gebildet werden können. Zusammen mit der Konkatenation, also dem Aneinanderhängen von Wörtern, und dem leeren Wort als neutralem Element bildet A* ein Monoid, das freie Monoid über A.

Ein Homomorphismus zwischen zwei freien Monoiden heißt Morphismus. Er ist eindeutig durch die Bilder der einzelnen Buchstaben bestimmt. Für Wörter x, y und z ist x ein Präfix, y ein Faktor und z ein Suffix des Wortes xyz.

Historisch untersuchte Axel Thue Anfang des 20. Jahrhunderts Wörter erstmals systematisch. In den 1950er-Jahren trieben unter anderem französische Mathematiker um Marcel Schützenberger sowie russische Mathematiker um Sergei Petrowitsch Nowikow und Sergei Iwanowitsch Adjan die Forschung voran. Ein 1983 unter dem Pseudonym M. Lothaire erschienenes Buch fasste viele damalige Ergebnisse zusammen.

Periodizität und kritische Faktorisierungen

Für ein Wort w = a₁ … aₙ heißt eine natürliche Zahl p eine Periode von w, wenn aᵢ = aᵢ₊ₚ für jede natürliche Zahl i ≤ n − p gilt. Die Periode eines Wortes ist seine kürzeste Periode.

Der Satz von Fine und Wilf besagt: Hat ein Wort der Länge n die Perioden p und q, dann ist auch d eine Periode, wobei d der größte gemeinsame Teiler von p und q ist, sofern n ≥ p + q − d gilt.

Zwei Wörter heißen präfixkompatibel beziehungsweise suffixkompatibel, wenn eines ein Präfix beziehungsweise Suffix des anderen ist. Ein Wort x ist eine Wiederholung zwischen zwei Wörtern u und v, wenn x mit u präfixkompatibel und mit v suffixkompatibel ist. Die lokale Periode von uv zwischen u und v ist die Länge der kürzesten solchen Wiederholung. Eine Faktorisierung eines Wortes ist kritisch, wenn seine Periode und seine lokale Periode gleich sind. Jedes Wort mit mindestens Länge 2 besitzt eine kritische Faktorisierung.

Ein unendliches Wort a₁a₂a₃… heißt irgendwann periodisch, wenn natürliche Zahlen k und p existieren, sodass aᵢ = aᵢ₊ₚ für jede natürliche Zahl i ≥ k gilt. Andernfalls heißt es aperiodisch.

Morphismen und Wortgleichungen

Ein Morphismus heißt nicht löschend, wenn er kein Wort auf das leere Wort abbildet. Ist f ein nicht löschender Morphismus mit f(a) = aw für einen Buchstaben a und ein nicht leeres Wort w, dann ist

limₙ→∞ fⁿ(a) = awf(w)f²(w)f³(w)…

ein Fixpunkt von f. Ein solches unendliches Wort wird morphisch genannt. Beispiele sind das Thue-Morse-Wort mit f(0) = 01 und f(1) = 10 sowie das Fibonacci-Wort mit g(0) = 01 und g(1) = 0.

Eine Wortgleichung ist eine Gleichung, in der Wörter als Unbekannte auftreten. Formal ist sie ein Paar (L, R) ∈ (A ∪ X)* × (A ∪ X). Dabei ist A ein Alphabet und X ein dazu disjunktes Alphabet der Unbekannten. Eine Lösung ist ein Morphismus f: (A ∪ X) → A*, der alle Buchstaben aus A auf sich selbst abbildet und f(L) = f(R) erfüllt. Die Unbekannten werden also durch geeignete Wörter ersetzt.

Für die Gleichung xy = yx bestehen die Lösungen aus Morphismen mit x ↦ wᵐ und y ↦ wⁿ für ein Wort w und natürliche Zahlen m und n. Die Frage, ob eine Wortgleichung überhaupt eine Lösung besitzt, heißt Erfüllbarkeitsproblem für Wortgleichungen. Dieses Problem ist entscheidbar.

Defect Effect, Komplexität und Muster

Der Defect Effect ist ein wichtiges Resultat der Kombinatorik auf Wörtern. Er besagt, dass n Wörter, die eine nichttriviale Relation erfüllen, als Produkt von n − 1 Wörtern ausgedrückt werden können.

Die Komplexitätsfunktion pₓ: ℕ₀ → ℕ₀ eines unendlichen Wortes x ordnet jeder nicht negativen Ganzzahl die Anzahl der verschiedenen Faktoren dieser Länge im Wort zu. Untersucht wird vor allem das Wachstum dieser Funktion. Ein Sturmsches Wort erfüllt pₓ(n) = n + 1 für alle n ∈ ℕ₀. Weil pₓ(1) = 2 gelten muss, besteht ein Sturmsches Wort aus genau zwei verschiedenen Buchstaben. Sturmsche Wörter sind bezüglich der Komplexitätsfunktion minimal unter allen aperiodischen Wörtern. Das Fibonacci-Wort ist ein Beispiel.

Ein Wort w über einem Alphabet A enthält ein Muster m ∈ X*, wenn es einen nicht löschenden Morphismus f: X* → A* gibt, sodass f(m) ein Faktor von w ist. Andernfalls vermeidet w das Muster m. Ein Muster m heißt auf A vermeidbar, wenn ein unendliches Wort über A existiert, das m vermeidet.

Auf einem Alphabet mit zwei Buchstaben ist das Muster x² nicht vermeidbar, weil es bereits in jedem Wort der Länge 4 enthalten ist. Bei drei oder mehr Buchstaben kann man x² dagegen in quadratfreien Wörtern vermeiden. Das Thue-Morse-Wort vermeidet die Muster x³ und xyxyx.

Konjugierte und Lyndonwörter

Die Konjugierten eines Wortes w sind seine zirkulären Verschiebungen. Es handelt sich um Wörter uv, für die w = vu gilt.

Ein Lyndonwort ist ein Wort, das bezüglich einer lexikographischen Ordnung kleiner ist als alle seine Konjugierten. Für jedes Wort existiert eine eindeutige Zerlegung in eine lexikographisch monoton fallende Folge von Lyndonwörtern.