YES Problem: +(x,y) -> +(y,x) +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) +(+(x,y),z) -> +(x,+(y,z)) Proof: AT confluence processor Complete TRS T' of input TRS: +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) +(0(),y) -> y +(s(x53),y) -> s(+(x53,y)) +(x,y) -> +(y,x) +(+(x,y),z) -> +(x,+(y,z)) T' = (P union S) with TRS P:+(x,y) -> +(y,x) +(+(x,y),z) -> +(x,+(y,z)) TRS S:+(x,0()) -> x +(x,s(y)) -> s(+(x,y)) +(0(),y) -> y +(s(x53),y) -> s(+(x53,y)) S is left-linear and P is reversible. CP(S,S) = 0() = 0(), s(x53) = s(+(x53,0())), s(+(0(),x273)) = s(x273), s(+(s(x53),x275)) = s(+(x53,s(x275))), s(y) = s(+(0(),y)), s(+(x278,0())) = s(x278), s(+(x280,s(y))) = s(+(s(x280),y)) CP(S,P union P^-1) = x = +(0(),x), +(x,y) = +(x,+(y,0())), +(x,z) = +(x,+(0(),z)), y = +(0(),y), +(x,y) = +(+(x,y),0()), s(+(x,x324)) = +(s(x324),x), s(+(+(x,y),x326)) = +(x,+(y,s(x326))), +(s(+(x,x328)),z) = +(x,+(s(x328),z)), s(+(y,x330)) = +(s(x330),y), +(x,s(+(y,x332))) = +(+(x,y),s(x332)), y = +(y,0()), +(y,z) = +(0(),+(y,z)), x = +(x,0()), +(y,z) = +(+(0(),y),z), +(x,z) = +(+(x,0()),z), s(+(x338,y)) = +(y,s(x338)), +(s(+(x340,y)),z) = +(s(x340),+(y,z)), s(+(x342,x)) = +(x,s(x342)), s(+(x344,+(y,z))) = +(+(s(x344),y),z), +(x,s(+(x346,z))) = +(+(x,s(x346)),z) PCP_in(P union P^-1,S) = We have to check termination of S: Matrix Interpretation Processor: dim=1 interpretation: [0] = 0, [+](x0, x1) = 4x0 + 2x1 + 1, [s](x0) = x0 + 7 orientation: +(x,0()) = 4x + 1 >= x = x +(x,s(y)) = 4x + 2y + 15 >= 4x + 2y + 8 = s(+(x,y)) +(0(),y) = 2y + 1 >= y = y +(s(x53),y) = 4x53 + 2y + 29 >= 4x53 + 2y + 8 = s(+(x53,y)) problem: Qed