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=2 interpretation: [f#](x0, x1) = [1 1]x0 + [0 1]x1, [1 0] [h](x0) = [0 0]x0, [0 0] [0] [f](x0, x1) = [1 0]x0 + x1 + [1], [0] [a] = [0] orientation: f#(x,f(a(),y)) = [1 1]x + [0 1]y + [1] >= [1 0]x + [0 1]y + [1] = f#(f(a(),h(f(a(),x))),y) f#(x,f(a(),y)) = [1 1]x + [0 1]y + [1] >= [1 0]x + [0 1]y + [1] = f#(a(),f(f(a(),h(f(a(),x))),y)) f#(x,f(a(),y)) = [1 1]x + [0 1]y + [1] >= [0 1]x = f#(a(),x) [0 0] [0] [0 0] [0] f(x,f(a(),y)) = [1 0]x + y + [2] >= [1 0]x + y + [2] = 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