Monotone Algebren, Interpretationen

Beispiel:

• Regel ba→aab
• Ableitung bba→baab→aabab→aaaabb
• Interpretation in $\mathbb {N}$ : [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 $\iff$ ∃ wfmA, die mit R kompatibel ist.