YES TRS: active(zeros()) -> mark(cons(0(),zeros())) active(tail(cons(X,XS))) -> mark(XS) mark(zeros()) -> active(zeros()) mark(cons(X1,X2)) -> active(cons(mark(X1),X2)) mark(0()) -> active(0()) mark(tail(X)) -> active(tail(mark(X))) cons(mark(X1),X2) -> cons(X1,X2) cons(X1,mark(X2)) -> cons(X1,X2) cons(active(X1),X2) -> cons(X1,X2) cons(X1,active(X2)) -> cons(X1,X2) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) max/plus interpretations on N: active_A(x1) = max{4, x1} active#_A(x1) = max{3, 5 + x1} zeros_A = 8 zeros#_A = 4 mark_A(x1) = max{2, 2 + x1} mark#_A(x1) = max{1, 8 + x1} cons_A(x1,x2) = max{5, 1 + x1, -3 + x2} cons#_A(x1,x2) = max{0, 0, -4 + x2} 0_A = 3 0#_A = 0 tail_A(x1) = max{1, 7 + x1} tail#_A(x1) = max{10, 0} precedence: tail > active > mark > zeros = cons > 0