Wohlfundierte monotone Algebren

• Beispiel:
  • Regel ba→aab, Abl. bba→baab→aabab→aaaabb
  • Interpretation in $\mathbb {N}$: [a](x) = x + 1,[b](x) = 3x,[ε] = 0
  • [bba] = 9 > [baab] = 6 > [aabab] = … > [aaaabb] = …
• Def: (D, > ,[⋅]) ist wohlfundierte monotone Algebra
  • wohlfundiert: SN( > ), keine unendl. absteigende Kette
  • monoton: ∀c∈Σ, x∈D, y∈D : x > y⇒[c](x) > [c](y)

    allgemein: Monotonie in jedem Argument einzeln

• Def: monotone Algebra ist kompatibel mit R:
  • Kompatibilität: ∀(l, r)∈R, x∈D : [l](x) > [r](x)

  wg. Monotonie folgt daraus u→_Rv⇒[u] > [v]

• Satz: SN(→_R) $\iff$ ∃ wfmA, die mit R kompatibel ist.