Definition, Motivation

• Def: ein ARS A = (U,→) ist ein Universum U

  und ein System von Relationen →_i⊆U² für i∈I.

  für I = {1} oder I = {1, 2} Notation (U,→), (U,→₁,→₂)

• das abstrahiert von konkreten Reduktionssystemen, z.B.
  • U Spielpositionen, →₁,→₂: Züge für Spieler 1,2
  • U Terme, →_i durch Ersetzungs/Vereinfachungs-regeln
  • U Speicherbelegungen, → durch Programm-Befehle
• wichtige Eigenschaften von ARS sind
  • Termination (keine unendlichen Ketten)
  • Konfluenz (Zusammenführbarkeit divergenter Ketten)