YES TRS: 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 max/plus interpretations on N: sum_A(x1,x2) = max{27, -1, 3 + x2} sum#_A(x1,x2) = max{20, 21, 23} cons_A(x1,x2) = max{4, 8 + x1, 14 + x2} cons#_A(x1,x2) = max{2, 3, 23} s_A(x1) = max{7, -12} s#_A(x1) = max{22, 22} 0_A = 16 0#_A = 20 nil_A = 0 nil#_A = 0 weight_A(x1) = max{0, 1 + x1} weight#_A(x1) = max{0, -3 + x1} precedence: nil = weight > sum > cons > s = 0