Wort-Ersetzungs-Systeme

Id: rewriting.tex,v 1.1 2004/12/14 12:36:40 waldmann Exp

Berechnungs-Modell (Markov-Algorithmen)

Regelmenge R $ \subseteq$ $ \Sigma^{*}_{}$×$ \Sigma^{*}_{}$

Regel-Anwendung: u$ \to_{R}^{}$v$ \iff$$ \exists$x, z $ \in$ $ \Sigma^{*}_{}$,(l, r) $ \in$ R : u = x . l . z $ \wedge$ x . r . z = v.

Beispiel: Bubble-Sort: {ba$ \to$ab, ca$ \to$ac, cb$ \to$bc}

Beispiel: Potenzieren: ab$ \to$bba

Aufgaben: gibt es unendlich lange Rechnungen für: R1 = {1000$ \to$0001110}, R2 = {aabb$ \to$bbbaaa}?



Johannes Waldmann 2005-01-28