YES(?,O(n^3)) TRS: { f mark X -> mark f X, f ok X -> ok f X, g ok X -> ok g X, active f X -> f active X, active f f a() -> mark f g f a(), proper f X -> f proper X, proper g X -> g proper X, proper a() -> ok a(), top mark X -> top proper X, top ok X -> top active X } DUP: We consider a non-duplicating system. Trs: { f mark X -> mark f X, f ok X -> ok f X, g ok X -> ok g X, active f X -> f active X, active f f a() -> mark f g f a(), proper f X -> f proper X, proper g X -> g proper X, proper a() -> ok a(), top mark X -> top proper X, top ok X -> top active X } Matrix Interpretation: Interpretation class: triangular [X2] [1 0 3][X2] [0] [top]([X1]) = [0 0 0][X1] + [0] [X0] [0 0 0][X0] [0] [X2] [1 1 0][X2] [1] [ok]([X1]) = [0 1 0][X1] + [1] [X0] [0 0 1][X0] [0] [X2] [1 3 0][X2] [2] [proper]([X1]) = [0 1 0][X1] + [1] [X0] [0 0 1][X0] [0] [X2] [1 1 3][X2] [0] [active]([X1]) = [0 1 1][X1] + [0] [X0] [0 0 0][X0] [0] [1] [a] = [0] [3] [X2] [1 3 3][X2] [3] [mark]([X1]) = [0 1 2][X1] + [2] [X0] [0 0 0][X0] [0] [X2] [1 2 0][X2] [0] [g]([X1]) = [0 1 0][X1] + [1] [X0] [0 0 0][X0] [0] [X2] [1 2 2][X2] [0] [f]([X1]) = [0 1 0][X1] + [1] [X0] [0 0 1][X0] [0] Qed