YES 1 decompositions #0 ----------- 1: +(x,0()) -> x 2: +(x,s(y)) -> s(+(x,y)) 3: +(0(),y) -> y 4: +(s(x),y) -> s(+(x,y)) 5: dbl(0()) -> 0() 6: dbl(s(x)) -> s(s(dbl(x))) 7: +(+(x,y),z) -> +(x,+(y,z)) 8: +(x,y) -> +(y,x) 9: dbl(+(x,y)) -> +(dbl(x),dbl(y)) @Jouannaud and Kirchner's criterion --- R 1: +(x,0()) -> x 2: +(x,s(y)) -> s(+(x,y)) 3: +(0(),y) -> y 4: +(s(x),y) -> s(+(x,y)) 5: dbl(0()) -> 0() 6: dbl(s(x)) -> s(s(dbl(x))) 7: +(+(x,y),z) -> +(x,+(y,z)) 8: +(x,y) -> +(y,x) 9: dbl(+(x,y)) -> +(dbl(x),dbl(y)) --- S 1: +(x,0()) -> x 2: +(x,s(y)) -> s(+(x,y)) 3: +(0(),y) -> y 4: +(s(x),y) -> s(+(x,y)) 5: dbl(0()) -> 0() 6: dbl(s(x)) -> s(s(dbl(x))) 7: +(+(x,y),z) -> +(x,+(y,z)) 8: +(x,y) -> +(y,x) 9: dbl(+(x,y)) -> +(dbl(x),dbl(y))