Ableitungsmuster

• gegeben: Ersetzungssystem,
• gesucht: untere Schranken für Ableitungskomplexität,

  d. h. Ableitungsmuster mit Parametern und induktiven Beweisen

Beispiel R = {ab→ba}

linear: ∀k≥0 : a^kb→^kba^k, quadratisch: ∀k, l≥0 : a^kb^l→^k⋅lb^la^k,

Beispiel S = {ab→baa}

linear: ∀k≥0 : a^kb→^*ba^2k

exponentiell: ∀l≥0 : ab^l→^*b^la^2l