YES (VAR x1 x0 x y z) (RULES i(f(x1,x0)) -> f(i(x0),i(x1)) i(i(i(x0))) -> i(x0) f(f(x0,x1),i(x1)) -> x0 f(x0,i(i(x1))) -> f(x0,x1) f(e(),x0) -> i(i(x0)) f(f(x0,i(x1)),x1) -> x0 i(e()) -> e() f(x,e()) -> x f(i(x),x) -> e() f(x,f(y,z)) -> f(f(x,y),z) ) (COMMENT Termination is shown by EKBO with interpretations on natural numbers f_A(x1,x2) = x1 + x2 + 1 i_A(x1) = x1 e_A = 1 f#_A(x1,x2) = x2 e#_A = 0 weights w0 = 1 w(f) = 0 w(i) = 0 w(e) = 1 and precedence: i > e > f )