Id: rewriting.tex,v 1.1 2004/12/14 12:36:40 waldmann Exp
Berechnungs-Modell (Markov-Algorithmen)
Regelmenge R ×
Regel-Anwendung: uvx, z ,(l, r) R : u = x . l . z x . r . z = v.
Beispiel: Bubble-Sort: {baab, caac, cbbc}
Beispiel: Potenzieren: abbba
Aufgaben: gibt es unendlich lange Rechnungen für: R1 = {10000001110}, R2 = {aabbbbbaaa}?