Beispiel:
- Regel
ba→aab
- Ableitung
bba→baab→aabab→aaaabb
- Interpretation in
:
[a](x) = x + 1,[b](x) = 3x,[ε] = 0
-
[baa] = 9 > [baab] = 6 > [aabab] = … > [aaaabb] = …
Def:
(D, > ,[⋅])
ist wohlfundierte monotone Algebra
- keine unendlichen absteigenden Ketten in (D, > )
- Monotonie:
∀c∈Σ, x∈D, y∈D : x > y⇒[c](x) > [c](y)
Def: Algebra ist kompatibel mit R
:
- Kompatibilität:
∀(l, r)∈R, x∈D : [l](x) > [r](x)
Satz: →R
terminiert
∃
wfmA,
die mit R
kompatibel ist.
Johannes Waldmann
2015-12-11