Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Kombinatorik der Wortmorphismen

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2018 bis 2023
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 389613931
 
Erstellungsjahr 2024

Zusammenfassung der Projektergebnisse

Dieses Projekt war auf zwei Hauptrichtungen ausgerichtet. Einerseits wollten wir Methoden, die in der Kombinatorik und der Theorie der formalen Sprache verwurzelt sind, entwickeln, welche es uns ermöglichen die Komplexität der Lösung von (restriktierten) Wortgleichungen besser zu verstehen und neue Einblicke in die Struktur ihrer Lösungsmengen zu bekommen. Andererseits wollten wir auch eine allgemeinere Untersuchung der kombinatorischen und algorithmischen Eigenschaften von Wortmorphismen durchführen, die über den Bereich der Wortgleichungen hinausgeht. Das folgende Ergebnis ist das Bedeutendste, welches wir im Bezug auf Wortgleichungen erzielt haben. Ausgehend von der Tatsache, dass es für quadratische Wortgleichungen einen auf Umschreibregeln basierenden Algorithmus gibt, der einen gerichteten Graphen erzeugt, welcher alle Lösungen der Gleichung beschreibt, konnten wir zeigen, dass dieser Graph im Fall von regulären Wortgleichungen - also solchen, bei denen jede Variable höchstens einmal auf jeder Seite der Gleichung vorkommt - gute kombinatorische Eigenschaften hat. Insbesondere waren wir in der Lage, polynomielle Schranken für seinen Durchmesser, seine Größe und seine DAG-Breite zu zeigen und einige tiefere Einblicke in die Symmetrien seiner Struktur zu gewinnen. Infolgedessen konnten wir mittels eines kombinatorischen Beweises zeigen, dass das Entscheidungsproblem (Existenz einer Lösung) für reguläre Wortgleichungen in NP liegt, und somit NP-vollständig ist. Dieses bahnbrechende Ergebnis bildet den Abschluss einer längeren Forschungsreihe über reguläre und quadratische Wortgleichungen und stellt eine der größten Klassen von Wortgleichungen dar, deren Erfüllbarkeit in NP ist. Diese Ergebnisse wurden durch eine Reihe von Untersuchungen sowohl theoretischer als auch praktischer Natur ergänzt, die sich mit der Entscheidbarkeit anderer Klassen des String Constraint Solving befassten (d.h. Wortgleichungen mit zusätzlichen linearen Längenbeschränkungen und Zugehörigkeiten zu formalen Sprachen). Im Bereich der Untersuchung der kombinatorischen und algorithmischen Eigenschaften von Wortmorphismen stammen unsere wichtigsten Ergebnisse aus der Untersuchung von Morphismen, welche Wörter auf ihre Menge von Subsequenzen mit einer bestimmten Länge abbilden. Insbesondere haben wir ein seit langem offenes Problem gelöst, das von Simon in den 1970er Jahren formuliert wurde, indem wir gezeigt haben, dass man in linearer Zeit die größte Zahl k berechnen kann, so dass zwei Eingabewörter genau die gleiche Menge von Subsequenzen der Länge k haben. Dieses Ergebnis war eine Kombination aus tiefgreifenden kombinatorischen Beobachtungen und der Konstruktion neuer effizienter Datenstrukturen. Darüber hinaus eröffnete es einen vielversprechenden und sehr ergiebigen Forschungszweig in Bezug auf kombinatorische Mustererkennung und Analyseproblemen von Strings auf Basis ihrer Subsequenz-Mengen.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2025 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung