Prof. Dr. Ulf Schmerl Institut für Informatik Dr. Ralph Matthes der Universität München

Übungsblatt 2

zur Vorlesung Termersetzungssysteme im Sommersemester 2001 11. Mai 2001

1. Zeige Königs Lemma: Ist → terminierend und endlich verzweigend (d. h., zu jedem x gibt es nur endlich viele y mit x → y), dann ist → global endlich, d. h., zu jedem x gibt es nur endlich viele y mit x →^{∗} y. Zeige dies einerseits mittels Noetherscher Induktion, andererseits durch Argumentation mithilfe unendlicher Reduktionsfolgen.

2. [2, Exercise 2.11] Zeige, daß der folgende Vorgang immer zum Ende kommt: Gegeben sei eine Urne mit endlich vielen blauen und roten Kugeln. In jedem Schritt werde eine beliebige Kugel gezogen. Ist sie rot, so werden endlich viele blaue Kugeln in die Urne geworfen.

3. [2, Exercise 2.16] Zeige, daß die folgenden Berechnungsregeln eine Funktion ack definieren, die für alle nichtnegativen ganzen Zahlen m, n die Berechnung der nichtnegativen ganzen Zahl ack(m, n) erlaubt:

ack(0, n) = n + 1
ack(m + 1, 0) = ack(m, 1)
ack(m + 1, n + 1) = ack(m, ack(m + 1, n))

4. [2, Exercise 2.33] Die Reduktionsrelation → habe folgende Eigenschaft (eine Abschwächung der Diamant-Eigenschaft): Wenn x → y und x → z mit y ≠ z, dann gibt es ein u mit y → u und z → u. Zeige, daß für jedes normalisierbare x alle Reduktionsfolgen aus x bis zu einer Normalform die gleiche Länge besitzen.

5. [2, Exercise 2.36] Zeige, daß zwei stark kommutierende Reduktionsrelationen kommutieren.

6. [1, Aufgabe 1.3.7(a)] Gegeben sei eine zweielementige Menge {a, b}, und > sei gegeben durch a > b. Zeige, daß sich die Erweiterung >_{mul} von > auf Multimengen nicht als transitiver Abschluß einer endlich verzweigenden Reduktionsrelation darstellen läßt.

Literatur

[1] Jürgen Avenhaus. Reduktionssysteme—Rechnen und Schließen in gleichungsdefinierten Strukturen. Springer Verlag, 1995.

[2] Franz Baader and Tobias Nipkow. Term Rewriting and All That. Cambridge University Press, 1998.

Besprechung in der Übung am 16. Mai 2001.