YES (VAR x0 x1 x y z) (RULES g(1(),*(x0,x1)) -> *(g(1(),x1),g(1(),x0)) *(*(x0,g(1(),x1)),x1) -> x0 *(*(x0,x1),g(1(),x1)) -> x0 *(g(1(),x0),x0) -> 1() *(x,g(1(),x)) -> 1() g(1(),g(1(),x0)) -> x0 i(x0) -> g(1(),x0) f(x0,x1) -> g(x0,*(g(1(),x1),x0)) *(1(),x0) -> x0 *(x0,1()) -> x0 g(1(),1()) -> 1() *(x,*(y,z)) -> *(*(x,y),z) ) (COMMENT Termination is shown by ELPO with interpretations on natural numbers *_A(x1,x2) = x1 + x2 + 1 1_A = 1 i_A(x1) = x1 g_A(x1,x2) = x2 f_A(x1,x2) = x1 + x2 + 2 *#_A(x1,x2) = x2 1#_A = 0 i#_A(x1) = x1 g#_A(x1,x2) = 0 f#_A(x1,x2) = x2 and precedence: f > i > g > * > 1 )