Problem: f(g(x)) -> h(g(x),g(x)) f(s(x)) -> h(s(x),s(x)) g(x) -> s(x) Proof: Church Rosser Transformation Processor (star): strict: f(0)(s(0)(x)) -> h(0)(s(0)(x)) f(0)(s(0)(x)) -> h(1)(s(0)(x)) f(0)(g(0)(x)) -> h(0)(g(0)(x)) f(0)(g(0)(x)) -> h(1)(g(0)(x)) weak: g(0)(x) -> s(0)(x) critical peaks: 1 f(s(x)) <-2|0[]- f(g(x)) -0|[]-> h(g(x),g(x)) Matrix Interpretation Processor: dim=1, lab=right interpretation: [h(1)](x0) = 2x0 + 1, [h(0)](x0) = 2x0, [f(0)](x0) = 2x0 + 2, [s(0)](x0) = x0, [g(0)](x0) = x0 orientation: f(0)(s(0)(x)) = 2x + 2 >= 2x = h(0)(s(0)(x)) f(0)(s(0)(x)) = 2x + 2 >= 2x + 1 = h(1)(s(0)(x)) f(0)(g(0)(x)) = 2x + 2 >= 2x = h(0)(g(0)(x)) f(0)(g(0)(x)) = 2x + 2 >= 2x + 1 = h(1)(g(0)(x)) g(0)(x) = x >= x = s(0)(x) problem: strict: weak: g(0)(x) -> s(0)(x) Matrix Interpretation Processor: dim=1, lab=right interpretation: [s(0)](x0) = x0, [g(0)](x0) = x0 + 1 orientation: g(0)(x) = x + 1 >= x = s(0)(x) problem: strict: weak: Shift Processor lab=left (dd): strict: f(g(x)) -> f(s(x)) f(g(x)) -> h(g(x),g(x)) f(s(x)) -> h(s(x),s(x)) h(g(x),g(x)) -> h(g(x),s(x)) h(g(x),s(x)) -> h(s(x),s(x)) f(s(x)) -> h(s(x),s(x)) h(g(x),g(x)) -> h(s(x),g(x)) h(s(x),g(x)) -> h(s(x),s(x)) weak: f(g(x)) -> h(g(x),g(x)) f(s(x)) -> h(s(x),s(x)) g(x) -> s(x) LPO Processor: precedence: f > s ~ h ~ g problem: strict: f(g(x)) -> f(s(x)) h(g(x),g(x)) -> h(g(x),s(x)) h(g(x),s(x)) -> h(s(x),s(x)) h(g(x),g(x)) -> h(s(x),g(x)) h(s(x),g(x)) -> h(s(x),s(x)) weak: g(x) -> s(x) LPO Processor: precedence: g > s ~ h ~ f problem: strict: weak: Shift Processor (ldh) lab=left (force): strict: weak: Decreasing Processor: The following diagrams are decreasing: peak: f(s(x)) <-2|0[1,0,0]- f(g(x)) -0|[1,0,0]-> h(g(x),g(x)) joins: f(s(x)) -1|[0,0,0]-> h(s(x),s(x)) h(g(x),g(x)) -2|1[0,0,0]-> h(g(x),s(x)) -2|0[0,0,0]-> h(s(x),s(x)) Qed