Kombinatorik auf Wörtern

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Wortkombinatorik)
Zur Navigation springen Zur Suche springen

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.

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]

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 | Quelltext 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 .

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]

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 | Quelltext 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]

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]

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 | Quelltext 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]

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 | Quelltext 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.