YES Problem: g(f(f(h(x))),y) -> g(g(f(h(x)),f(f(h(x)))),y) f(x) -> g(x,f(x)) h(x) -> g(f(x),x) g(x,y) -> h(g(f(x),f(y))) Proof: Church Rosser Transformation Processor: strict: weak: critical peaks: 5 g(g(f(h(x44)),f(f(h(x44)))),y) <-0|[]- g(f(f(h(x44))),y) -3|[]-> h(g(f(f(f(h(x44)))),f(y))) g(g(f(h(x)),f(f(h(x)))),y) <-1|0[]- g(f(f(h(x))),y) -0|[]-> g(g(f(h(x)),f(f(h(x)))),y) g(f(g(h(x),f(h(x)))),y) <-1|0,0[]- g(f(f(h(x))),y) -0|[]-> g(g(f(h(x)),f(f(h(x)))),y) g(f(f(g(f(x),x))),y) <-2|0,0,0[]- g(f(f(h(x))),y) -0|[]-> g(g(f(h(x)),f(f(h(x)))),y) h(g(f(f(f(h(x)))),f(y))) <-3|[]- g(f(f(h(x))),y) -0|[]-> g(g(f(h(x)),f(f(h(x)))),y) Shift Processor lab=left (dd) (force): strict: g(f(f(h(x44))),y) -> g(g(f(h(x44)),f(f(h(x44)))),y) g(f(f(h(x44))),y) -> h(g(f(f(f(h(x44)))),f(y))) g(g(f(h(x44)),f(f(h(x44)))),y) -> h(g(f(g(f(h(x44)),f(f(h(x44))))),f(y))) h(g(f(f(f(h(x44)))),f(y))) -> h(g(f(g(f(h(x44)),f(f(h(x44))))),f(y))) g(f(f(h(x))),y) -> g(g(f(h(x)),f(f(h(x)))),y) g(f(f(h(x))),y) -> g(g(f(h(x)),f(f(h(x)))),y) g(f(f(h(x))),y) -> g(f(g(h(x),f(h(x)))),y) g(f(f(h(x))),y) -> g(g(f(h(x)),f(f(h(x)))),y) g(f(g(h(x),f(h(x)))),y) -> g(g(g(h(x),f(h(x))),f(g(h(x),f(h(x))))),y) g(g(f(h(x)),f(f(h(x)))),y) -> g(g(f(h(x)),f(g(h(x),f(h(x))))),y) g(g(f(h(x)),f(g(h(x),f(h(x))))),y) -> g(g(g(h(x),f(h(x))),f(g(h(x),f(h(x))))),y) g(f(g(h(x),f(h(x)))),y) -> g(g(g(h(x),f(h(x))),f(g(h(x),f(h(x))))),y) g(g(f(h(x)),f(f(h(x)))),y) -> g(g(g(h(x),f(h(x))),f(f(h(x)))),y) g(g(g(h(x),f(h(x))),f(f(h(x)))),y) -> g(g(g(h(x),f(h(x))),f(g(h(x),f(h(x))))),y) g(f(f(h(x))),y) -> g(f(f(g(f(x),x))),y) g(f(f(h(x))),y) -> g(g(f(h(x)),f(f(h(x)))),y) g(f(f(g(f(x),x))),y) -> g(g(f(g(f(x),x)),f(f(g(f(x),x)))),y) g(g(f(h(x)),f(f(h(x)))),y) -> g(g(f(h(x)),f(f(g(f(x),x)))),y) g(g(f(h(x)),f(f(g(f(x),x)))),y) -> g(g(f(g(f(x),x)),f(f(g(f(x),x)))),y) g(f(f(g(f(x),x))),y) -> g(g(f(g(f(x),x)),f(f(g(f(x),x)))),y) g(g(f(h(x)),f(f(h(x)))),y) -> g(g(f(g(f(x),x)),f(f(h(x)))),y) g(g(f(g(f(x),x)),f(f(h(x)))),y) -> g(g(f(g(f(x),x)),f(f(g(f(x),x)))),y) g(f(f(h(x))),y) -> h(g(f(f(f(h(x)))),f(y))) g(f(f(h(x))),y) -> g(g(f(h(x)),f(f(h(x)))),y) h(g(f(f(f(h(x)))),f(y))) -> h(g(f(g(f(h(x)),f(f(h(x))))),f(y))) g(g(f(h(x)),f(f(h(x)))),y) -> h(g(f(g(f(h(x)),f(f(h(x))))),f(y))) weak: g(f(f(h(x))),y) -> g(g(f(h(x)),f(f(h(x)))),y) f(x) -> g(x,f(x)) h(x) -> g(f(x),x) g(x,y) -> h(g(f(x),f(y))) Shift Processor (ldh) lab=left (force): strict: weak: Rule Labeling Processor: strict: weak: rule labeling (right): g(f(f(h(x))),y) -> g(g(f(h(x)),f(f(h(x)))),y): 3 f(x) -> g(x,f(x)): 0 h(x) -> g(f(x),x): 0 g(x,y) -> h(g(f(x),f(y))): 0 Shift Processor lab=left (par): strict: weak: Decreasing Processor (par): The following diagrams are decreasing: peak: h(g(f(f(f(h(x)))),f(y))) <-3|[==1,=>0]- g(f(f(h(x))),y) -0|[==1,?=3]-> g(g(f(h(x)),f(f(h(x)))),y) joins (1): h(g(f(f(f(h(x)))),f(y))) -1|0,0,0[==1,=>0]-> h(g(f(g(f(h(x)),f(f(h(x))))),f(y))) g(g(f(h(x)),f(f(h(x)))),y) -3|[==1,=>0]-> h(g(f(g(f(h(x)),f(f(h(x))))),f(y))) peak: g(f(f(g(f(x),x))),y) <-2|0,0,0[==1,=>0]- g(f(f(h(x))),y) -0|[ ==1,?=3]-> g(g(f(h(x)),f(f(h(x)))),y) joins (1): g(f(f(g(f(x),x))),y) -1|0[==1,=>0]-> g(g(f(g(f(x),x)),f(f(g(f(x),x)))),y) g(g(f(h(x)),f(f(h(x)))),y) -2|0,1,0,0[==1,=>0]-> g(g(f(h(x)),f(f(g(f(x),x)))),y) -2| 0,0,0[==1,=>0]-> g(g(f(g(f(x),x)),f(f(g(f(x),x)))),y) peak: g(f(g(h(x),f(h(x)))),y) <-1|0,0[==1,=>0]- g(f(f(h(x))),y) -0| [==1,?=3]-> g(g(f(h(x)),f(f(h(x)))),y) joins (1): g(f(g(h(x),f(h(x)))),y) -1|0[==1,=>0]-> g(g(g(h(x),f(h(x))),f(g(h(x),f(h(x))))),y) g(g(f(h(x)),f(f(h(x)))),y) -1|0,1,0[==1,=>0]-> g(g(f(h(x)),f(g(h(x),f(h(x))))),y) -1| 0,0[==1,=>0]-> g(g(g(h(x),f(h(x))),f(g(h(x),f(h(x))))),y) peak: g(g(f(h(x)),f(f(h(x)))),y) <-1|0[==1,=>0]- g(f(f(h(x))),y) -0| [==1,?=3]-> g(g(f(h(x)),f(f(h(x)))),y) joins (1): peak: g(g(f(h(x44)),f(f(h(x44)))),y) <-0|[==1,=?3]- g(f(f(h(x44))),y) -3| [==1,>=0]-> h(g(f(f(f(h(x44)))),f(y))) joins (1): g(g(f(h(x44)),f(f(h(x44)))),y) -3|[==1,>=0]-> h(g(f(g(f(h(x44)),f(f(h(x44))))),f(y))) h(g(f(f(f(h(x44)))),f(y))) -1|0,0,0[==1,>=0]-> h(g(f(g(f(h(x44)),f(f(h(x44))))),f(y))) Qed