Kombinatorik der Wortmorphismen

• Antragsteller: Professor Dr. Florin Manea
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 389613931

Kombinatorische Mustererkennung (combinatorial pattern matching) ist ein Teilgebiet der theoretischen Informatik, welches Fragestellungen zu den kombinatorischen und algorithmischen Eigenschaften endlicher und unendlicher Folgen (in diesem Zusammenhang auch Wörter oder Zeichenketten genannt) umfasst. Dieses Gebiet hat Berührungspunkte mit Algebra, Kombinatorik, Komplexitätstheorie und Algorithmik, und es besitzt vielfältige Anwendungen in der Datenkompression, Kryptographie, formalen Sprachtheorie sowie Bioinformatik und Data Mining. Eines der Kernthemen ist das Verständnis der kombinatorischen und algorithmischen Eigenschaften von Wortmorphismen. Wir planen in diesem Projekt, Wortmorphismen sowohl aus algorithmischer als auch mathematischer Sicht zu untersuchen.In der algorithmischen Sichtweise betrachten wir das Erfüllbarkeitsproblem von Wortgleichungen. Seien zwei Wörter über Konstanten- und Variablensymbolen gegeben, dann interessieren wir uns für Verfahren, mit denen die Variablen durch endliche Wörter über dem Konstantenalphabet ersetzt werden können, so dass beide Wörter ein identisches Resultat ergeben, d.h. wir suchen nach einem entsprechenden Morphismus zur Lösung der Wortgleichung. Die genaue Zeitkomplexität des Erfüllbarkeitsproblems von Wortproblemen ist jedoch bisher nicht bekannt: es kann mit linearem nichtdeterministischen Platzbedarf gelöst werden und ist NP-schwer. Das weist darauf hin, dass im Allgemeinen die Berechnung von Wortmorphismen, welche eine Menge von gegebenen Bedingungen erfüllen, schwer ist. Wir planen die Untersuchung des Erfüllbarkeitsproblems allgemeiner Wortgleichungen. Für bestimmte nicht-triviale, eingeschränkte Klassen, welche durch verschiedene numerische und strukturelle Parameter definiert sind, erwarten wir, effiziente Algorithmen zu finden.In der mathematischen Sichtweise planen wir die Untersuchung kombinatorischer und algebraischer Eigenschaften von Wortmorphismen. Hierbei sind wir besonders an dem Studium struktureller und kombinatorischer Eigenschaften von sogenannten Gleichheitsmengen (equality sets) interessiert. Eine Gleichheitsmenge ist die Menge von Wörtern, für die zwei gegebene Morphismen identisch sind. Diese Forschungsfragen haben einen tiefen Bezug zu anderen Gebieten, wie der Berechenbarkeitstheorie. Zum Beispiel kann das bekannte Postsche Korrespondenzproblem als das Leerheitsproblem der Gleichheitsmenge zweier gegebener Morphismen aufgefasst werden. Darüber hinaus ist die Frage nach der Größe der algebraischen Dimension von unabhängigen Wortgleichungssystemen von Interesse. Es ist z.B. ein lange offenes Problem, die maximale Größe von unabhängigen Wortgleichungen über eine feste Variablenmenge zu bestimmen. Die Lösung solcher Fragestellungen scheint ein tiefgehendes Verständnis der kombinatorischen Eigenschaften von Morphismen, welche die Lösungen eines Gleichungssystems repräsentieren, zu erfordern.

• DFG-Verfahren: Sachbeihilfen