YES O(n^3) TRS: { b(y, 0()) -> y, c(b(y, c(x))) -> c(c(b(a(0(), 0()), y))), a(x, y) -> b(x, b(0(), c(y))) } DUP: We consider a non-duplicating system. Trs: { b(y, 0()) -> y, c(b(y, c(x))) -> c(c(b(a(0(), 0()), y))), a(x, y) -> b(x, b(0(), c(y))) } Matrix Interpretation: Interpretation class: triangular [X5] [X2] [1 0 3][X5] [1 2 2][X2] [2] [a]([X4], [X1]) = [0 1 2][X4] + [0 0 0][X1] + [1] [X3] [X0] [0 0 1][X3] [0 0 0][X0] [0] [X2] [1 2 0][X2] [0] [c]([X1]) = [0 0 0][X1] + [0] [X0] [0 0 0][X0] [3] [1] [0] = [0] [0] [X5] [X2] [1 0 2][X5] [1 0 0][X2] [0] [b]([X4], [X1]) = [0 1 2][X4] + [0 0 3][X1] + [1] [X3] [X0] [0 0 1][X3] [0 0 0][X0] [0] Qed