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