Wortprobleme für Gruppen, ab 1900

• das war eine Motivation für Knuth und Bendix
• Monoid-Darstellung (für Gruppe ähnlich): verwendet
  • endliche Menge von Generatoren (Buchstaben)
  • endliche Menge von Gleichungen (Wortpaaren)
  〈a, b | ab = ba〉 für {a, b}^*/ $\approx_{E}^{}$ mit E = {ab→ba}
• Kombinatorische Gruppentheorie (Walter Dyck, 1881) https://zenodo.org/record/1942346/preview/article.pdf
• $\approx_{E}^{}$ ist das Wortproblem (Max Dehn 1911)
• ist einer der Ursprünge für die spätere Entwicklung der Begriffe Algorithmus und Berechenbarkeit.
• es gibt E, für die $\approx_{E}^{}$ nicht entscheidbar ist (Novikov 1955)