Id: rewriting.tex,v 1.1 2006-10-16 19:50:57 waldmann Exp
Berechnungs-Modell (Markov-Algorithmen)
Regelmenge
R
×
Regel-Anwendung:
uv
x, z
,(l, r)
R : u = x . l . z
x . r . z = v.
Beispiel: Bubble-Sort:
{baab, ca
ac, cb
bc}
Beispiel: Potenzieren:
abbba
Aufgaben: gibt es unendlich lange Rechnungen für:
R1 = {10000001110}, R2 = {aabb
bbbaaa}?