YES 3: +(0(),x2) -> x2 4: +(s(x1),x2) -> s(+(x1,x2)) 5: dbl(0()) -> 0() 6: dbl(s(x1)) -> s(s(dbl(x1))) 7: +(+(x1,x2),x3) -> +(x1,+(x2,x3)) 8: +(x1,x2) -> +(x2,x1) 9: dbl(+(x1,x2)) -> +(dbl(x1),dbl(x2)) @Jouannaud and Kirchner's criterion --- R 3: +(0(),x2) -> x2 4: +(s(x1),x2) -> s(+(x1,x2)) 5: dbl(0()) -> 0() 6: dbl(s(x1)) -> s(s(dbl(x1))) 7: +(+(x1,x2),x3) -> +(x1,+(x2,x3)) 8: +(x1,x2) -> +(x2,x1) 9: dbl(+(x1,x2)) -> +(dbl(x1),dbl(x2)) --- S 3: +(0(),x2) -> x2 4: +(s(x1),x2) -> s(+(x1,x2)) 5: dbl(0()) -> 0() 6: dbl(s(x1)) -> s(s(dbl(x1))) 7: +(+(x1,x2),x3) -> +(x1,+(x2,x3)) 8: +(x1,x2) -> +(x2,x1) 9: dbl(+(x1,x2)) -> +(dbl(x1),dbl(x2)) NOTE: input TRS is reduced original is 1: +(x1,0()) -> x1 2: +(x1,s(x2)) -> s(+(x1,x2)) 3: +(0(),x2) -> x2 4: +(s(x1),x2) -> s(+(x1,x2)) 5: dbl(0()) -> 0() 6: dbl(s(x1)) -> s(s(dbl(x1))) 7: +(+(x1,x2),x3) -> +(x1,+(x2,x3)) 8: +(x1,x2) -> +(x2,x1) 9: dbl(+(x1,x2)) -> +(dbl(x1),dbl(x2)) reduced to 3: +(0(),x2) -> x2 4: +(s(x1),x2) -> s(+(x1,x2)) 5: dbl(0()) -> 0() 6: dbl(s(x1)) -> s(s(dbl(x1))) 7: +(+(x1,x2),x3) -> +(x1,+(x2,x3)) 8: +(x1,x2) -> +(x2,x1) 9: dbl(+(x1,x2)) -> +(dbl(x1),dbl(x2))