FU Berlin, Fachbereich
Mathematik und Informatik, Institut
für Informatik
Vortrag des Informatik-Kolloquiums
Neuere Ergebnisse auf dem Gebiet der Wortgleichungen
Prof. Dr. Volker Diekert, Stuttgart
Die existentielle Theorie von Wortgleichungen und von Gleichungen über freien Gruppen ist entscheidbar. Dies sind zwei Resultate von
Makanin, die in mehrfacher Hinsicht Bekanntheit erlangten. Die Ergebnisse sind von grundlegender Bedeutung, sie sind schwierig, Makanins Algorithmen
sind komplex und die Laufzeit extrem hoch.
Insbesondere durch Beiträge von Plandowski hat sich die Situation in den letzten Jahren vereinfacht und wir verfügen heute bei Gleichungen
über freien Gruppen über einen polynomial platzbeschränkten Algorithmus, während vorher nur ein beweisbar nicht-primitiver
Algorithmus zur Verfügung stand. Die neuen Ideen führten darüber hinaus zu weiteren Entscheidbarkeitsresultaten.
In dem Vortrag gebe ich eine Übersicht und stelle einige offene Probleme vor.