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