Wort- und Term-Ersetzung

• Wort (Folge) als Term (Baum, Pfad) auffassen

  Beispiel: abaab bedeutet a(b(a(a(b(ε))))).

• Wortersetzungssystem (SRS):

  Menge von Regeln, Regel: Paar von Wörtern

  ab→ba bedeutet a(b(x))→b(a(x))

• Alle Aussagen über TRS gelten auch für SRS,

• SRS (als Berechnungsmodell) sind Turing-vollständig, denn eine TM ist (im wesentlichen) ein SRS
• für viele Anwendungen sind TRS natürlich (algebraische Beschreibung, Terme mit Symbolen der Stelligket > 1)
• zahlreiche Methoden für TRS wurden zuerst für SRS erfunden und untersucht (z.B. für Termination)