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