Content area
Pattern und ihre Sprachen
Pattern, d. h. endliche Wörter aus Variablen und Terminalsymbolen, stellen eine kom-pakte, elegante und natürliche Methode dar, gewisse kontextsensitive Sprachen zu re-präsentieren. Ein Pattern erzeugt ein Wort durch eine Substitution, die alle Variablen im Pattern durch beliebige endliche Wörter über einem festen Terminalalphabet ersetzt. Die Patternsprache eines Pattern ist somit die Menge aller Wörter, die durch die Substituti-on des Pattern gebildet werden können; etwas formaler ist eine Patternsprache also die Menge aller Bilder des Pattern unter beliebigen terminalerhaltenden Homomorphismen. Wenn wir beispielsweise das Pattern az, arab, (mit Variablen 11,12 und Termi-nalsymbolen a, b) betrachten, liegen folglich (unter anderem) die Wörter w₁=aabbba, W₂:abababab und waaabaa in der von a erzeugten Patternsprache L(a), woge-gen die Beispielworter w₁=ba, w: babbba und wabba nicht von a erzeugt werden können.
Die Untersuchung von Pattern in Wörtern lässt sich bis zu Thue [103] zurückverfolgen und zählt mittlerweile zu den etablierten Teilgebieten der Wortkombinatorik (s. Cas-saigne [17]), während die explizite Verwendung von Pattern als Sprachgeneratoren von Angluin [4] eingeführt wurden. In Angluins Definition ist es nicht erlaubt, Variablen löschend zu ersetzen, daher wird diese Klasse von Patternsprachen in der Literatur im Allgemeinen als NE-Patternsprachen bezeichnet („NE" steht in diesem Fall für non-erasing"). Ebenfalls häufig betrachtet werden die von Shinohara [102] eingeführten so-genannten E-Patternsprachen" („E" wie erasing" oder extended"); bei dieser Sprach-klasse ist die löschende Substitution gestattet. Im obigen Beispiel ist somit das Wort W3 zwar in der E-Patternsprache, nicht jedoch in der NE-Patternsprache von a enthalten. Durch diesen scheinbar kleinen definitorischen Unterschied besitzen die beiden Sprachklassen sehr unterschiedliche Eigenschaften. Beispielsweise lässt sich das Äqui-valenzproblem (d. h. die Frage, ob zwei Pattern die gleiche Sprache erzeugen) für NE-Patternsprachen trivial in Polynomialzeit entscheiden, während die Entscheidbarkeit des Aquivalenzproblems für E-Patternsprachen ein schweres und seit rund 30 Jahren offenes Problem darstellt (s. Ohlebusch und Ukkonen [79]. Reidenbach [87]).
Beide Sprachklassen wurden zuerst in der Induktiven Inferenz, einem Teilgebiet der (mathematischen) Lerntheorie, eingeführt. Ziel dieser Betrachtungen war es, zu gege-benen Mengen von Wörtern effektiv Pattern zu finden, die diese Wörter beschreiben. Inzwischen wurden Patternsprachen auch in der Theorie der formalen Sprachen ausgie-big untersucht. Wegen ihrer einfachen Definition kommen Pattern und ihre Sprachen in einer Vielzahl anderer Gebiete der Informatik und der diskreten Mathematik vor.
Aufgrund der einfachen Definition von Patternsprachen ließe sich vermuten, dass sich die meisten interessanten Eigenschaften einer Patternsprache direkt aus dem sie erzeu-genden Wort ablesen lassen. Insbesondere sollte sich daher leicht entscheiden lassen, ob zwei Pattern die gleiche oder vergleichbare Sprachen erzeugen (d. h. ob eine Äquivalenz-oder Inklusionsbeziehung vorliegt), und ob ein Wort in der Sprache eines Patterns ist (das sogenannte „Wortproblem"). Tatsächlich ist diese Vermutung aber in den meisten Fällen ein Trugschluss beispielsweise ist das Inklusionsproblem im Allgemeinen unent-scheidbar, und das Wortproblem NP-vollständig.
Die vorliegende Dissertation beschäftigt sich mit verschiedenen Aspekten des Inklu-sionsproblems. Den eigentlichen Hauptteil der Arbeit bilden die Kapitel 3 bis 7, die sich sich grob in zwei Teile unterteilen lassen.
Der erste Teil, der aus den Kapiteln 3 und 4 besteht, befasst sich direkt mit dem Inklusionsproblem für Patternsprachen und wendet eine in diesem Kontext entwickelte Technik auf eine in der Praxis weit verbreitete Erweiterung der regulären Ausdrücke an.