Inklusion von Patternsprachen und verwandte Probleme

Ein Pattern ist ein Wort aus Variablen und Terminalsymbolen. Die von einem Pattern p erzeugte Patternsprache ist die Menge aller Terminalwörter, die durch eine uniforme Ersetzung der Variablen in p durch Terminalwörter erzeugt werden können. So beschreibt das Pattern p = ax y ax (wobei x und y Variablen sind und a ein Terminal ist) die Menge aller Wörter, die ein Wort der Form ax sowohl als Präfix, als auch als Suffix haben. 

Wegen ihrer einfachen Definition besitzen Patternsprachen eine Vielzahl von Verbindungen zu verschiedenen anderen Gebieten der theoretischen Informatik und Mathematik, unter anderem zur Wortkombinatorik, Logik und der Theorie freier Halbgruppen. Andererseits führen viele der üblichen sprachtheoretischen Fragestellungen bei Patternsprachen zu kombinatorischen Problemen von überraschender Schwierigkeit.

Im Vortrag werden zuerst einige dieser Verbindungen vorgestellt. Der erste Teil des Vortrags widmet sich verschiedenen Aspekten des Inklusionsproblems von Patternsprachen. Neben der Entscheidbarkeit des Inklusionsproblems für Sprachen, die von Pattern mit beschränkter Variablenzahl erzeugt werden, betrachten wir verschiedene Aspekte der Minimierbarkeit von regulären Ausdrücken mit Rückreferenzen.

Der zweite Teil des Vortrags handelt von deskriptiven Pattern; d.h. derjenigen Pattern, die die (hinsichtlich der Inklusion) kleinsten Verallgemeinerungen einer gegebenen Sprache erzeugen. Hierbei befassen wir uns mit der Existenz und Auffindbarkeit von deskriptiven Pattern für beliebige Sprachen.