Periodizität

Gegeben sei ein Wort ${\displaystyle w=a_{1}\dots a_{n}}$. Eine natürliche Zahl ${\displaystyle p}$ ist eine Periode von ${\displaystyle w}$, wenn ${\displaystyle a_{i}=a_{i+p}}$ für jede natürliche Zahl ${\displaystyle 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 ${\displaystyle n}$ mit den Perioden ${\displaystyle p}$ und ${\displaystyle q}$ auch ${\displaystyle d}$, definiert als größter gemeinsamer Teiler von ${\displaystyle p}$ und ${\displaystyle q}$, als Periode hat, wenn ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle a_{1}a_{2}a_{3}\dots }$ heißt irgendwann periodisch, wenn natürliche Zahlen ${\displaystyle k}$ und ${\displaystyle p}$ existieren mit ${\displaystyle a_{i}=a_{i+p}}$ für jede natürliche Zahl ${\displaystyle 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 ${\displaystyle f(a)=aw}$ für einen Buchstaben a und ein nicht leeres Wort w, so ist das unendliche Wort ${\displaystyle \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 ${\displaystyle \lim _{n\to \infty }f^{n}(0)}$ mit ${\displaystyle f(0)=01}$ und ${\displaystyle f(1)=10}$ und das Fibonacci-Wort ${\displaystyle \lim _{n\to \infty }g^{n}(0)}$ mit ${\displaystyle g(0)=01}$ und ${\displaystyle g(1)=0}$.

Wortgleichungen

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

Formal ist eine Wortgleichung ein Paar ${\displaystyle (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 ${\displaystyle f\colon (A\cup X)^{*}\to A^{*}}$ mit ${\displaystyle 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 ${\displaystyle xy=yx}$ mit Unbekannten ${\displaystyle x}$ und ${\displaystyle y}$. Die Lösungen dafür sind Morphismen mit ${\displaystyle x\mapsto w^{n}}$ und ${\displaystyle y\mapsto w^{m}}$ für ein Wort ${\displaystyle w}$ und natürliche Zahlen ${\displaystyle n}$ und ${\displaystyle 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 ${\displaystyle n}$ Wörter, die eine nichttriviale Relation erfüllen, als Produkt von ${\displaystyle n-1}$ Wörtern ausgedrückt werden können.

Komplexität

Die Komplexitätsfunktion ${\displaystyle 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 ${\displaystyle p_{x}(n)=n+1}$ für alle ${\displaystyle n\in \mathbb {N} _{0}}$. Weil ${\displaystyle 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 ${\displaystyle m\in X^{*}}$, wenn ein nicht löschender Morphismus ${\displaystyle f\colon X^{*}\to A^{*}}$ existiert, sodass ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle x^{3}}$ und ${\displaystyle xyxyx}$.

Lyndonwörter

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