YES O(n^3) TRS: { c(X) -> d(activate(X)), f(X) -> n__f(X), f(f(X)) -> c(n__f(n__g(n__f(X)))), d(X) -> n__d(X), activate(X) -> X, activate(n__f(X)) -> f(activate(X)), activate(n__g(X)) -> g(X), activate(n__d(X)) -> d(X), h(X) -> c(n__d(X)), g(X) -> n__g(X) } DUP: We consider a non-duplicating system. Trs: { c(X) -> d(activate(X)), f(X) -> n__f(X), f(f(X)) -> c(n__f(n__g(n__f(X)))), d(X) -> n__d(X), activate(X) -> X, activate(n__f(X)) -> f(activate(X)), activate(n__g(X)) -> g(X), activate(n__d(X)) -> d(X), h(X) -> c(n__d(X)), g(X) -> n__g(X) } Matrix Interpretation: Interpretation class: triangular [X2] [1 0 0][X2] [2] [g]([X1]) = [0 0 0][X1] + [0] [X0] [0 0 0][X0] [0] [X2] [1 4 4][X2] [7] [h]([X1]) = [0 1 4][X1] + [4] [X0] [0 0 0][X0] [2] [X2] [1 0 0][X2] [0] [n__d]([X1]) = [0 0 0][X1] + [0] [X0] [0 0 0][X0] [0] [X2] [1 2 2][X2] [4] [activate]([X1]) = [0 1 0][X1] + [0] [X0] [0 0 1][X0] [0] [X2] [1 0 0][X2] [1] [d]([X1]) = [0 0 0][X1] + [0] [X0] [0 0 0][X0] [0] [X2] [1 4 1][X2] [2] [f]([X1]) = [0 1 4][X1] + [4] [X0] [0 0 0][X0] [4] [X2] [1 0 0][X2] [1] [n__g]([X1]) = [0 0 0][X1] + [0] [X0] [0 0 0][X0] [0] [X2] [1 4 0][X2] [0] [n__f]([X1]) = [0 1 4][X1] + [4] [X0] [0 0 0][X0] [4] [X2] [1 2 2][X2] [6] [c]([X1]) = [0 0 0][X1] + [0] [X0] [0 0 0][X0] [0] Qed