Gleichungen über Wörtern, Spuren und anderen Strukturen

• Applicant: Professor Dr. Volker Diekert
• Subject Area: Theoretical Computer Science
• Term: from 2001 to 2004
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5325220

Die Theorie von Wortgleichungen ist ein klassischer Untersuchungsgegenstand der Theoretischen Informatik. Sie gilt als technisch sehr anspruchsvoll und schwierig. Zunächst schien es fragwürdig, ob es überhaupt ein allgemeines Lösungsverfahren für Wortgleichungen geben könnte. Makanin beantwortete diese Frage 1977 und 1983 in zwei Arbeiten zwar positiv, doch deuteten seine Ergebnisse auf eine extrem hohe Komplexität der zugehörigen Algorithmen hin. Durch eine unerwartete Entwicklung, angestoßen durch drei Arbeiten von Plandowski, konnte die Komplexität in den letzten Jahren drastisch verringert werden. Durch die dabei entwickelten Methoden eröffnen sich erstmals Perspektiven, praktische Anwendungen ernsthaft anzugreifen. Die zentrale Vermutung auf dem Gebiet stellt gleichzeitig das Leitmotiv des Projekts dar: Man zeige, daß die Lösbarkeit von Wortgleichungssystemen NP-vollständig ist. Für einen möglichen Beweis dieser Vermutung müssen neue Techniken entwickelt werden. Selbst wenn das obige Ziel nicht erreicht werden kann, so erwarten wir durch Seiteneffekte konkrete Resultate. Das Forschungsvorhaben GWSS soll in enger Kooperation mit internationalen Partnern durchgeführt werden, mit denen thematisch schon auf diesem Gebiet zusammengearbeitet wurde....

• DFG Programme: Research Grants