Gleichungen in freien Monoiden

Sei u = v eine Gleichung, in der sowohl die Buchstaben eines endlichen Alphabets A als auch Unbestimmte aus X auftreten. Man sagt, dass diese Gleichung lösbar ist, wenn es eine Abbildung \phi: X \to A^* gibt, sodass \phi(u) und \phi(v) identische Worte sind. Es war über viele Jahre ein offenes Problem, ob es überhaupt entscheidbar ist, ob eine solche Gleichung eine Lösung hat oder nicht. Erst im Jahre 1977 hat G.S. Makanin die Entscheidbarkeit dieses Problems bewiesen.

Seitdem ist Makanins Algorithmus der Gegenstand zahlreicher Untersuchungen, die u.a. die folgenden Ziele verfolgen:

In diesem Seminar sollen einige neuere Arbeiten über Makanins Algorithmus behandelt werden.