Aufgaben

Signatur (mit Stelligkeiten): $\Sigma$ = {e⁰, s¹, p², m², h²}

• R_p = {p(e, y)$\to$y, p(s(x), y)$\to$s(p(x, y))}
• R_m = R_p $\cup$ {m(e, y)$\to$e, m(s(x), y)$\to$p(m(x, y), y)}
• R_h = R_m $\cup$ {h(x, e)$\to$s(e), h(x, s(y))$\to$m(h(x, y), x)}

Fragen (leicht):

• Menge der R_h-Normalformen?
• Normalformen (Existenz? Eindeutigkeit?) von: p(s(p(s(e), s(e))), s(e)), m(s(s(e)), s(s(e))), h(s(s(e)), s(s(s(e)))).

(schwerer) $\Sigma$ = {a², d⁰}, R = {a(a(d, x), y)$\to$a(x, a(x, y))}: Normalformen? Ableitungslängen?