Termersetzung/Anwendungen

Termersetzung ist

• Grundlage für funktionale Programmierung

  (Auswertung, Kompilation, Verifikation)

• Grundlage für Symbolisches Rechnen
• (Grundlage für XML-Transformationen mit XSLT, ...)

Für Anwendungen wichtig sind die Eigenschaften

• Termination (SN) (keine unendlich langen Rechnungen)
• Konfluenz (CR,UNR) (eindeutige Ergebnisse)
• Ableitungskomplexität (Länge von Rechnungen als Funktion der Startgröße)

das ist aber alles unentscheidbar (wg. Turing-Vollst.)