##  [Lösung des Wortproblems](/de/node/62348) 

 Definition

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

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

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

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

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

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

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

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

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.