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

Übungsblatt 1

zur Vorlesung Termersetzungssysteme im Sommersemester 2001 30. April 2001

1. [1, Aufgabe 1.1.1] Sei → gegeben durch n → m :⇔ m = \frac{3n}{2} ∨ m = \frac{7n}{5} mit den positiven ganzen Zahlen als Trägermenge.

• Zeige, daß → terminiert.

• Gib die Menge der Normalformen an.

• Was ist die Normalform von 150?

• Zeige, daß 14 ↔ 10 und 28 ↔^{∗} 45.

2. [1, Aufgabe 1.1.2] Sei → gegeben durch n → m :⇔ m = \frac{3n}{2} ∨ m = \frac{4n}{3} mit den positiven ganzen Zahlen als Trägermenge.

• Zeige, daß → nicht terminiert.

• Gib die Menge der Normalformen an.

• Zeige, daß 40 ↔^{∗} 45.

3. [2, Exercise 2.1]

• Ist der reflexive Abschluß des transitiven Abschlusses von → dasselbe wie der transitive Abschluß des reflexiven Abschlusses von →, und wie verhalten sich die beiden zum transitiven reflexiven Abschluß →^{∗}?

• Ist der symmetrische Abschluß des transitiven Abschlusses von → dasselbe wie der transitive Abschluß des symmetrischen Abschlusses von →?

4. [2, Exercise 2.2] Zeige, daß → genau dann konfluent und normalisierend ist, wenn jedes Element der Trägermenge von → genau eine Normalform besitzt.

5. [2, Exercise 2.4] Zeige, daß →^{+} genau dann terminierend ist, wenn → es ist. Zeige dies einerseits über den Begriff der unendlichen Reduktionsfolgen, andererseits mittels Induktion über induktiv definierte Mengen, d. h. mittels Noetherscher Induktion.

6. [2, Exercise 2.32] Wenn → die Diamanteigenschaft hat, dann hat jedes Element der Trägermenge von → entweder keine Normalform, oder es ist bereits normal.

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 9. Mai 2001.