YES Problem: f(x,f(a(),y)) -> f(a(),f(f(a(),h(f(a(),x))),y)) Proof: DP Processor: DPs: f#(x,f(a(),y)) -> f#(a(),x) f#(x,f(a(),y)) -> f#(a(),h(f(a(),x))) f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) TRS: f(x,f(a(),y)) -> f(a(),f(f(a(),h(f(a(),x))),y)) EDG Processor: DPs: f#(x,f(a(),y)) -> f#(a(),x) f#(x,f(a(),y)) -> f#(a(),h(f(a(),x))) f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) TRS: f(x,f(a(),y)) -> f(a(),f(f(a(),h(f(a(),x))),y)) graph: f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) -> f#(x,f(a(),y)) -> f#(a(),x) f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) -> f#(x,f(a(),y)) -> f#(a(),h(f(a(),x))) f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) -> f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) -> f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) -> f#(x,f(a(),y)) -> f#(a(),x) f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) -> f#(x,f(a(),y)) -> f#(a(),h(f(a(),x))) f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) -> f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) -> f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) f#(x,f(a(),y)) -> f#(a(),x) -> f#(x,f(a(),y)) -> f#(a(),x) f#(x,f(a(),y)) -> f#(a(),x) -> f#(x,f(a(),y)) -> f#(a(),h(f(a(),x))) f#(x,f(a(),y)) -> f#(a(),x) -> f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) -> f#(a(),x) -> f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) SCC Processor: #sccs: 1 #rules: 3 #arcs: 12/16 DPs: f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) f#(x,f(a(),y)) -> f#(a(),x) TRS: f(x,f(a(),y)) -> f(a(),f(f(a(),h(f(a(),x))),y)) Matrix Interpretation Processor: dim=1 interpretation: [f#](x0, x1) = 2x0 + 2x1, [h](x0) = 0, [f](x0, x1) = 4x1 + 3, [a] = 0 orientation: f#(x,f(a(),y)) = 2x + 8y + 6 >= 2y + 6 = f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) = 2x + 8y + 6 >= 8y + 6 = f#(a(),f(f(a(),h(f(a(),x))),y)) f#(x,f(a(),y)) = 2x + 8y + 6 >= 2x = f#(a(),x) f(x,f(a(),y)) = 16y + 15 >= 16y + 15 = f(a(),f(f(a(),h(f(a(),x))),y)) problem: DPs: f#(x,f(a(),y)) -> f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) TRS: f(x,f(a(),y)) -> f(a(),f(f(a(),h(f(a(),x))),y)) Arctic Interpretation Processor: dimension: 1 interpretation: [f#](x0, x1) = x1, [h](x0) = 0, [f](x0, x1) = 1x1, [a] = 0 orientation: f#(x,f(a(),y)) = 1y >= y = f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) = 1y >= 1y = f#(a(),f(f(a(),h(f(a(),x))),y)) f(x,f(a(),y)) = 2y >= 2y = f(a(),f(f(a(),h(f(a(),x))),y)) problem: DPs: f#(x,f(a(),y)) -> f#(a(),f(f(a(),h(f(a(),x))),y)) TRS: f(x,f(a(),y)) -> f(a(),f(f(a(),h(f(a(),x))),y)) Matrix Interpretation Processor: dim=2 interpretation: [f#](x0, x1) = [2 0]x0 + [1 0]x1, [0] [h](x0) = [0], [0 1] [3 0] [f](x0, x1) = [2 0]x0 + [0 0]x1, [0] [a] = [1] orientation: f#(x,f(a(),y)) = [2 0]x + [3 0]y + [1] >= [3 0]y = f#(a(),f(f(a(),h(f(a(),x))),y)) [0 1] [9 0] [3] [9 0] [1] f(x,f(a(),y)) = [2 0]x + [0 0]y + [0] >= [0 0]y + [0] = f(a(),f(f(a(),h(f(a(),x))),y)) problem: DPs: TRS: f(x,f(a(),y)) -> f(a(),f(f(a(),h(f(a(),x))),y)) Qed