YES (VAR x1 x0 x2 y x z) (RULES symm(trans(x1,x0)) -> trans(symm(x0),symm(x1)) trans(x1,trans(symm(x1),x0)) -> x0 symm(h(x0)) -> h(symm(x0)) symm(f(x0)) -> f(symm(x0)) symm(g(x0)) -> g(symm(x0)) trans(x0,symm(x0)) -> refl() symm(symm(x0)) -> x0 symm(refl()) -> refl() g(refl()) -> refl() f(refl()) -> refl() h(refl()) -> refl() trans(x0,refl()) -> x0 trans(f(x1),trans(g(x0),x2)) -> trans(g(x0),trans(f(x1),x2)) trans(g(x0),trans(h(x1),x2)) -> trans(h(x1),trans(g(x0),x2)) trans(f(x1),trans(h(x0),x2)) -> trans(h(x0),trans(f(x1),x2)) trans(f(x0),trans(f(x1),x2)) -> trans(f(trans(x0,x1)),x2) trans(g(x0),trans(g(x1),x2)) -> trans(g(trans(x0,x1)),x2) trans(h(x0),trans(h(x1),x2)) -> trans(h(trans(x0,x1)),x2) trans(symm(x1),trans(x1,x0)) -> x0 trans(f(y),h(x)) -> trans(h(x),f(y)) trans(g(x),h(y)) -> trans(h(y),g(x)) trans(f(x),g(y)) -> trans(g(y),f(x)) trans(h(x),h(y)) -> h(trans(x,y)) trans(g(x),g(y)) -> g(trans(x,y)) trans(f(x),f(y)) -> f(trans(x,y)) trans(refl(),x) -> x trans(symm(x),x) -> refl() trans(trans(x,y),z) -> trans(x,trans(y,z)) ) (COMMENT Termination is shown by EKBO with interpretations on natural numbers trans_A(x1,x2) = x1 + x2 symm_A(x1) = x1 refl_A = 0 f_A(x1) = 2 g_A(x1) = 1 h_A(x1) = 0 trans#_A(x1,x2) = x1 refl#_A = 0 f#_A(x1) = 0 weights w0 = 1 w(trans) = 0 w(symm) = 0 w(refl) = 1 w(f) = 1 w(g) = 1 w(h) = 1 and precedence: symm > h > g > trans > f > refl )