Grenzen der Berechenbarkeit bei Problemen auf Wörtern

• Antragsteller: Professor Dr. Dirk Nowotka
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 437493335

In vielen Anwendungsfällen der Informatik liegt die sequenzielle Darstellung von Daten nahe. Sequenzen von Symbolen (Wörter) stellen daher eine fundamentale und allgegenwärtige Datenstruktur mit wichtigen Eigenschaften dar, welche eine Reihe von Anwendungen in Gebieten wie der Bioinformatik, dem Data Mining und der Datenkompression sowie rein mathematischen Gebieten wie der abstrakten Algebra findet. Darüber hinaus sind Wörter ein wichtiger Teil in klassischen Berechnungsmodellen und führen zu vielen erstaunlich einfach zu formulierenden unentscheidbaren Problemen wie dem Postschen Korrespondenzproblem (PKP). Solche Entscheidungsprobleme können oft auf natürliche Weise mit Parametern ausgestattet werden, wie zum Beispiel der Anzahl der Paare in einer PKP Instanz, so dass bei geeigneter Einschränkung entscheidbare Varianten des Problems erzeugt werden.Die eng verwandten Theorien der Mustersprachen (pattern languages) und Wortgleichungen enthalten Beispiele solcher grundlegender Probleme auf Wörtern, für welche viele naheliegende nummerische und nicht-nummerische Parameter existieren, die, bei geeigneter Besetzung, sowohl zu entscheidbaren wie auch unentscheidbaren Problemvarianten führen können. Das Ziel dieses Forschungsprojektes ist es, ein besseres Verständnis von der Grenze zwischen Entscheidbarkeit und Unentscheidbarkeit in diesem Kontext zu erlangen und wohlmotivierte Problemvarianten zu kategorisieren. Sowohl Wortgleichungen als auch sequenzielle Muster charakterisieren intrinsische strukturelle Eigenschaften von Wörtern. Es ist daher wenig verwunderlich, dass sie eine Reihe von Anwendungsgebieten besitzen, wie zum Beispiel Mustererkennung, maschinelles Lernen, Data Mining, IT-Sicherheit, Datenbanktheorie, Unifikation und Algebra.Es gibt darüber hinaus auch grundlegende Gründe, die genaue Grenze zwischen entscheidbaren und unentscheidbaren Problemvarianten zu untersuchen. Unentscheidbarkeitsbeweise werden überwiegend durch die Reduktion eines bekannten unentscheidbaren Problems auf das untersuchte Problem geführt. Eine Folge solcher Reduktionen kann sich schnell zu einer großen Lücke im strukturellen Verständnis der unentscheidbaren Problemvarianten ausweiten. Umgekehrt bedarf die Entdeckung neuer entscheidbarer Problemvarianten auch neuer Techniken des Herangehens und ist daher von intrinsischem Interesse für das Verständnis der entsprechenden Theorien und verwandter Themen.

• DFG-Verfahren: Sachbeihilfen