Der Entscheidungsprozess, zu bestimmen, ob zwei Wörter in den Erzeugern einer präsentierten algebraischen Struktur dasselbe Element im durch die Relationen definierten Quotienten darstellen; äquivalent ist die Entscheidung, ob ein gegebenes Wort das Identitätselement darstellt.

Prinzip

Wörter durch definierende Relationen auf eine kanonische oder Normalform reduzieren, sofern möglich, oder Entscheidungsverfahren (Umformungssysteme, Knuth–Bendix, Todd–Coxeter, gruppenspezifische Algorithmen) anwenden, die Gleichheit nachweisen oder Ungleichheit zertifizieren; die Entscheidbarkeit hängt von der Klasse der Präsentationen ab.

Demonstration

In einer freien Gruppe mit Erzeugern a und b löst sich das Wortproblem durch das Kürzen benachbarter inverser Paare: Um zu entscheiden, ob aba^{-1}b^{-1} die Identität ist, kürzt man systematisch aa^{-1} und bb^{-1}, bis keine Kürzungen mehr möglich sind, und schließt auf Identität, falls das leere Wort erreicht wird.

Fehlanwendung

Syntaktische Gleichheit (wörtlich identische Symbolfolgen) als Gruppen­gleichheit zu behandeln, ohne Relationen zu reduzieren, oder die Entscheidbarkeit für beliebige endlich präsentierte Gruppen vorauszusetzen — viele Präsentationen führen im Allgemeinen zu unentscheidbaren Wortproblemen.

Konsequenz

Ein korrektes Entscheidungsverfahren liefert entweder einen Algorithmus zur Berechnung von Normalformen und löst damit Gleichheitsanfragen, oder es zeigt die Unentscheidbarkeit in der Klasse; lösbare Wortprobleme erlauben effektive Berechnungen im Quotienten wie Zugehörigkeitsprüfungen und Homomorphismustests.

Umkehrung

Im Gegensatz steht das Konjugationsproblem (Entscheidung, ob zwei Elemente konjugiert sind) oder das Isomorphieproblem (Entscheidung über Isomorphie präsentierter Strukturen); die Umkehrung der Frage tauscht Gleichheit unter Relationen gegen Äquivalenz unter einem anderen Relationstyp.

Abgrenzung

Der Geltungsbereich wird durch die Klasse algebraischer Strukturen und Präsentationen begrenzt: Freie Gruppen, endliche Gruppen und viele Spezialklassen haben entscheidbare Wortprobleme; allgemeine endlich präsentierte Gruppen können unentscheidbare Wortprobleme aufweisen; Rechenressourcen und Terminierung sind praktische Grenzen.

Semantische Spannung

Wortproblem versus Identität formaler Sprachen oder syntaktische Gleichheit: Das Wortproblem ist semantisch (Gleichheit im durch Relationen definierten Quotienten), während syntaktische Identität Relationen ignoriert; es konkurriert auch konzeptionell mit Konjugations- und Zugehörigkeitsproblemen als zentrale Entscheidungsaufgabe in der Algebra.

Synthese

Die Lösung des Wortproblems führt die Frage der Gleichheit unter definierenden Relationen auf algorithmische Reduktion zu Normalformen oder auf die Anwendung von Entscheidungsverfahren zurück; sie ist der grundlegende algorithmische Gleichheitstest in präsentierten algebraischen Systemen, deren Lösbarkeit von der algebraischen Klasse und der gewählten Methode abhängt.