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

Übungsblatt 4

zur Vorlesung Termersetzungssysteme im Sommersemester 2001 28. Mai 2001

1. [1, Lemma 4.5.2] Eine Substitution σ_{1} heißt allgemeiner als eine Substitution σ_{2}, i. Z. σ_{1} ≲ σ_{2}, wenn es eine Substitution δ gibt mit σ_{2} = δσ_{1}. Zeige, daß ≲ eine strikte Ordnung ist (d. h., daß ≲ transitiv und irreflexiv ist).

2. [1, Exercise 4.10] Definiere Äquivalenz auf Substitutionen durch ∼:=≲ ∩ ≳. Zeige, daß σ_{1} ∼ σ_{2} genau dann gilt, wenn es eine Variablenumbenennung δ gibt mit σ_{2} = δσ_{1}.

3. [1, Exercise 4.10] Zeige, daß eine Substitution σ genau dann idempotent ist (d. h., σ = σσ), wenn Dom(σ) ∩ ⋃_{x∈Dom(σ)} V ar(σ(x)) = ∅

Literatur

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

Besprechung in der Übung am 30. Mai 2001.