YES Problem: sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(cons(0(),x),y) -> sum(x,y) sum(nil(),y) -> y weight(cons(n,cons(m,x))) -> weight(sum(cons(n,cons(m,x)),cons(0(),x))) weight(cons(n,nil())) -> n Proof: Matrix Interpretation Processor: dim=2 interpretation: [1 2] [1] [weight](x0) = [0 1]x0 + [1], [1] [nil] = [0], [1] [0] = [0], [1 0] [sum](x0, x1) = [0 0]x0 + x1, [1 0] [1] [cons](x0, x1) = x0 + [1 1]x1 + [0], [3] [s](x0) = x0 + [0] orientation: [1 0] [1 0] [1 0] [5] [1 0] [1 0] [1 0] [5] sum(cons(s(n),x),cons(m,y)) = m + [0 0]n + [0 0]x + [1 1]y + [0] >= m + [0 0]n + [0 0]x + [1 1]y + [0] = sum(cons(n,x),cons(s(m),y)) [1 0] [2] [1 0] sum(cons(0(),x),y) = [0 0]x + y + [0] >= [0 0]x + y = sum(x,y) [1] sum(nil(),y) = y + [0] >= y = y [3 2] [1 2] [5 2] [5] [1 0] [1 0] [4 2] [5] weight(cons(n,cons(m,x))) = [1 1]m + [0 1]n + [2 1]x + [2] >= [0 0]m + [0 0]n + [1 1]x + [1] = weight(sum(cons(n,cons(m,x)),cons(0(),x))) [1 2] [5] weight(cons(n,nil())) = [0 1]n + [2] >= n = n problem: sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) weight(cons(n,cons(m,x))) -> weight(sum(cons(n,cons(m,x)),cons(0(),x))) Matrix Interpretation Processor: dim=2 interpretation: [1 2] [weight](x0) = [0 0]x0, [0] [0] = [0], [1 1] [1 0] [sum](x0, x1) = [0 0]x0 + [0 0]x1, [1 0] [1 1] [cons](x0, x1) = [1 0]x0 + [2 0]x1, [1 0] [3] [s](x0) = [0 0]x0 + [0] orientation: [1 0] [2 0] [3 1] [1 1] [6] [1 0] [2 0] [3 1] [1 1] [3] sum(cons(s(n),x),cons(m,y)) = [0 0]m + [0 0]n + [0 0]x + [0 0]y + [0] >= [0 0]m + [0 0]n + [0 0]x + [0 0]y + [0] = sum(cons(n,x),cons(s(m),y)) [6 0] [3 0] [7 5] [4 0] [2 0] [6 4] weight(cons(n,cons(m,x))) = [0 0]m + [0 0]n + [0 0]x >= [0 0]m + [0 0]n + [0 0]x = weight(sum(cons(n,cons(m,x)),cons(0(),x))) problem: weight(cons(n,cons(m,x))) -> weight(sum(cons(n,cons(m,x)),cons(0(),x))) Matrix Interpretation Processor: dim=2 interpretation: [1 1] [weight](x0) = [0 0]x0, [0] [0] = [0], [1 0] [1 0] [sum](x0, x1) = [0 0]x0 + [0 0]x1, [2 2] [2 0] [0] [cons](x0, x1) = [0 0]x0 + [1 0]x1 + [1] orientation: [6 6] [2 2] [6 0] [1] [4 4] [2 2] [6 0] weight(cons(n,cons(m,x))) = [0 0]m + [0 0]n + [0 0]x + [0] >= [0 0]m + [0 0]n + [0 0]x = weight(sum(cons(n,cons(m,x)),cons(0(),x))) problem: Qed