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

Bearbeiten

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.[1]

Geschichte

Bearbeiten

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.[2]

Grundlegende Begriffe

Bearbeiten

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   eines Alphabets   ist die Menge der endlichen Wörter, die mit   gebildet werden können. Ist   ein Alphabet, dann bildet   mit der Konkatenation als Verknüpfung und dem leeren Wort als neutralem Element ein Monoid, das freie Monoid über  .

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

Sind   Wörter, so ist   ein Präfix,   ein Faktor und   ein Suffix des Wortes  .

Periodizität

Bearbeiten

Gegeben sei ein Wort  . Eine natürliche Zahl   ist eine Periode von  , wenn   für jede natürliche Zahl   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   mit den Perioden   und   auch  , definiert als größter gemeinsamer Teiler von   und  , als Periode hat, wenn   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   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.[3]

Ein unendliches Wort   heißt irgendwann periodisch, wenn natürliche Zahlen   und   existieren mit   für jede natürliche Zahl  , und aperiodisch, wenn das nicht der Fall ist.[4]

Morphismen

Bearbeiten

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ür einen Buchstaben a und ein nicht leeres Wort w, so ist das unendliche Wort   ein Fixpunkt von f und wird morphisch genannt. Beispiele sind das Thue-Morse-Wort   mit   und   und das Fibonacci-Wort   mit   und  .[5][6]

Wortgleichungen

Bearbeiten

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

Formal ist eine Wortgleichung ein Paar  , wobei A ein Alphabet und X ein dazu disjunktes Alphabet der Unbekannten ist. Eine Lösung ist ein Morphismus   mit  , 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   mit Unbekannten   und  . Die Lösungen dafür sind Morphismen mit   und   für ein Wort   und natürliche Zahlen   und  .

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

Defect Effect

Bearbeiten

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

Komplexität

Bearbeiten

Die Komplexitätsfunktion   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   für alle  . Weil   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.[9]

Vermeidbarkeit von Mustern

Bearbeiten

Sei A ein Alphabet und X ein dazu disjunktes Alphabet der Muster. Ein endliches oder unendliches Wort w über A enthält ein Muster  , wenn ein nicht löschender Morphismus   existiert, sodass   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   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   und  .[10]

Lyndonwörter

Bearbeiten

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

Einzelnachweise

Bearbeiten
  1. Juhani Karhumäki: Combinatorics on Words: A New Challenging Topic. In: TUCS Technical Report. Nr. 645, 2004, S. 2.
  2. Jean Berstel, Juhani Karhumäki: Combinatorics on Words – A Tutorial. In: Bulletin of the EATCS. Band 79, 2003, S. 3–4.
  3. Jean Berstel, Juhani Karhumäki: Combinatorics on Words – A Tutorial. In: Bulletin of the EATCS. Band 79, 2003, S. 9–12.
  4. M. Lothaire: Algebraic Combinatorics on Words. S. 259, doi:10.1017/CBO9781107326019.
  5. M. Lothaire: Combinatorics on Words. 2. Auflage. Cambridge University Press, 1997, S. 22, doi:10.1017/CBO9780511566097.
  6. Jean-Paul Allouche, Jeffrey Shallit: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003, S. 212, doi:10.1017/CBO9780511546563.
  7. M. Lothaire: Algebraic Combinatorics on Words. S. 342–383, doi:10.1017/CBO9781107326019.
  8. Jean Berstel, Juhani Karhumäki: Combinatorics on Words – A Tutorial. In: Bulletin of the EATCS. Band 79, 2003, S. 16–18.
  9. M. Lothaire: Algebraic Combinatorics on Words. S. 40–42, doi:10.1017/CBO9781107326019.
  10. M. Lothaire: Algebraic Combinatorics on Words. S. 98–101, doi:10.1017/CBO9781107326019.