YES TRS: active(f(g(X),Y)) -> mark(f(X,f(g(X),Y))) active(f(X1,X2)) -> f(active(X1),X2) active(g(X)) -> g(active(X)) f(mark(X1),X2) -> mark(f(X1,X2)) g(mark(X)) -> mark(g(X)) proper(f(X1,X2)) -> f(proper(X1),proper(X2)) proper(g(X)) -> g(proper(X)) f(ok(X1),ok(X2)) -> ok(f(X1,X2)) g(ok(X)) -> ok(g(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) max/plus interpretations on N: active_A(x1) = max{0, 12 + x1} active#_A(x1) = max{13, -1} f_A(x1,x2) = max{2, x1, -13} f#_A(x1,x2) = max{0, 10, -2} g_A(x1) = max{2, x1} g#_A(x1) = max{8, 6} mark_A(x1) = max{11, 12} mark#_A(x1) = max{5, 7} proper_A(x1) = max{2, 1} proper#_A(x1) = max{9, 11} ok_A(x1) = max{15, 13 + x1} ok#_A(x1) = max{7, 1} top_A(x1) = max{0, 1} top#_A(x1) = max{12, 2 + x1} precedence: f = top > active > g > mark = ok > proper