Kombinatorik auf Wörtern

Die Kombinatorik auf Wörtern ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik, das Struktur und Eigenschaften von Wörtern einer Gruppe (wie z. B. Wörtern einer formalen Sprache) untersucht.

Einordnung

Innerhalb der Mathematik steht die Kombinatorik auf Wörtern in Zusammenhang mit Algebra, Wahrscheinlichkeitstheorie, Zahlentheorie, Logik und symbolischer Dynamik. Innerhalb der theoretischen Informatik gibt es Verbindungen zur Komplexitätstheorie, Berechenbarkeitstheorie und Automatentheorie.

Darüber hinaus findet die Kombinatorik auf Wörtern auch in Physik und Biologie Anwendung.

Geschichte

Axel Thue gilt mit seinen Arbeiten zu Anfang des 20. Jahrhunderts als der Erste, der Wörter systematisch untersuchte. In den 1950er-Jahren bildeten sich eine Gruppe französischer Mathematiker um Marcel Schützenberger und eine Gruppe russischer Mathematiker um Sergei Petrowitsch Nowikow und Sergei Iwanowitsch Adjan, die die Forschung auf diesem Gebiet vorantrieben. Ein 1983 unter dem Pseudonym M. Lothaire erschienenes Buch fasst einen Großteil der damaligen Ergebnisse zusammen und trug bei zur Etablierung der Kombinatorik auf Wörtern als eigenes Forschungsgebiet.

Grundlegende Begriffe

Ein Alphabet ist eine endliche Menge, deren Elemente Buchstaben genannt werden. Ein Wort ist eine endliche oder unendliche Folge von Buchstaben eines Alphabets.

Die kleenesche Hülle $A^{*}$ eines Alphabets $A$ ist die Menge der endlichen Wörter, die mit $A$ gebildet werden können. Ist $A$ ein Alphabet, dann bildet $A^{*}$ mit der Konkatenation als Verknüpfung und dem leeren Wort als neutralem Element ein Monoid, das freie Monoid über $A$.

Ein Homomorphismus zwischen zwei freien Monoiden wird kurz als Morphismus bezeichnet. Morphismen sind eindeutig durch die Bilder der Buchstaben bestimmt.

Sind $x,y,z$ Wörter, so ist $x$ ein Präfix, $y$ ein Faktor und $z$ ein Suffix des Wortes $xyz$.

Themen

Periodizität

Gegeben sei ein Wort $w=a_{1}\dots a_{n}$. Eine natürliche Zahl $p$ ist eine Periode von $w$, wenn $a_{i}=a_{i+p}$ für jede natürliche Zahl $i\leq n-p$ gilt. Die Periode eines Wortes ist seine kürzeste Periode. Ein wichtiges Resultat ist der Satz von Fine and Wilf, der besagt, dass ein Wort der Länge $n$ mit den Perioden $p$ und $q$ auch $d$, definiert als größter gemeinsamer Teiler von $p$ und $q$, als Periode hat, wenn $n\geq p+q-d$ gilt.

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

Ein unendliches Wort $a_{1}a_{2}a_{3}\dots$ heißt irgendwann periodisch, wenn natürliche Zahlen $k$ und $p$ existieren mit $a_{i}=a_{i+p}$ für jede natürliche Zahl $i\geq k$, und aperiodisch, wenn das nicht der Fall ist.

Morphismen

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, so ist das unendliche Wort $\lim _{n\to \infty }f^{n}(a)=awf(w)f^{2}(w)f^{3}(w)\dots$ ein Fixpunkt von f und wird morphisch genannt. Beispiele sind das Thue-Morse-Wort $\lim _{n\to \infty }f^{n}(0)$ mit $f(0)=01$ und $f(1)=10$ und das Fibonacci-Wort $\lim _{n\to \infty }g^{n}(0)$ mit $g(0)=01$ und $g(1)=0$.

Wortgleichungen

Bei einer Wortgleichung handelt es sich um eine Gleichungen mit Wörtern als Unbekannten.

Formal ist eine Wortgleichung ein Paar $(L,R)\in (A\cup X)^{*}\times (A\cup X)^{*}$, wobei A ein Alphabet und X ein dazu disjunktes Alphabet der Unbekannten ist. Eine Lösung ist ein Morphismus $f\colon (A\cup X)^{*}\to A^{*}$ mit $f(L)=f(R)$, der alle Buchstaben aus A auf sie selbst abbildet. Die Unbekannten werden dabei mit geeigneten Wörtern so substituiert, dass die Gleichung erfüllt ist.

Ein Beispiel für eine Wortgleichung ist etwa $xy=yx$ mit Unbekannten $x$ und $y$. Die Lösungen dafür sind Morphismen mit $x\mapsto w^{n}$ und $y\mapsto w^{m}$ für ein Wort $w$ und natürliche Zahlen $n$ und $m$.

Die Frage, ob eine Wortgleichung eine Lösung hat, wird als Erfüllbarkeitsproblem für Wortgleichungen bezeichnet. Dieses ist entscheidbar.

Defect Effect

Ein wichtiges Resultat ist auch der Defect Effect. Dieser besagt, dass $n$ Wörter, die eine nichttriviale Relation erfüllen, als Produkt von $n-1$ Wörtern ausgedrückt werden können.

Komplexität

Die Komplexitätsfunktion $p_{x}\colon \mathbb {N} _{0}\to \mathbb {N} _{0}$ eines unendlichen Wortes x ist die Funktion, die jeder nicht negativen Ganzzahl die Anzahl der verschiedenen Faktoren dieser Länge im Wort zuordnet. Untersucht wird dabei in der Regel das Wachstumsverhalten der Funktion.

Ein Sturmsches Wort ist ein Wort x mit $p_{x}(n)=n+1$ für alle $n\in \mathbb {N} _{0}$. Weil $p_{x}(1)=2$ gelten muss, bestehen Sturmsche Wörter aus genau zwei verschiedenen Buchstaben. Sturmsche Wörter sind minimal bezüglich der Komplexitätsfunktion unter allen aperiodischen Wörtern. Ein Beispiel ist das Fibonacci-Wort.

Vermeidbarkeit von Mustern

Sei A ein Alphabet und X ein dazu disjunktes Alphabet der Muster. Ein endliches oder unendliches Wort w über A enthält ein Muster $m\in X^{*}$, wenn ein nicht löschender Morphismus $f\colon X^{*}\to A^{*}$ existiert, sodass $f(m)$ ein Faktor von w ist. Sonst vermeidet w das Muster m. Auf A ist m vermeidbar, wenn ein unendliches Wort über A existiert, das m vermeidet. So ist etwa bei einem Alphabet mit zwei Buchstaben das Muster $x^{2}$ nicht vermeidbar, weil es bereits in jedem Wort der Länge 4 enthalten ist. Bei drei oder mehr Buchstaben lässt es sich hingegen in Wörtern, die quadratfrei genannt werden, vermeiden. Das Thue-Morse-Wort vermeidet die Muster $x^{3}$ und $xyxyx$.

Lyndonwörter

→ Hauptartikel: Lyndonwort

Die Konjugierten eines Worts w sind alle zirkulären Verschiebungen, d. h. Wörter $uv$, sodass $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.