YES Problem: +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) +(0(),y) -> y +(s(x),y) -> s(+(x,y)) +(x,y) -> +(y,x) +(+(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(x),y) -> s(+(x,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(x),y) -> s(+(x,y)) S is left-linear and P is reversible. CP(S,S) = 0() = 0(), s(x) = s(+(x,0())), s(+(0(),x220)) = s(x220), s(+(s(x),x222)) = s(+(x,s(x222))), s(y) = s(+(0(),y)), s(+(x225,0())) = s(x225), s(+(x227,s(y))) = s(+(s(x227),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,x271)) = +(s(x271),x), s(+(+(x,y),x273)) = +(x,+(y,s(x273))), +(s(+(x,x275)),z) = +(x,+(s(x275),z)), s(+(y,x277)) = +(s(x277),y), +(x,s(+(y,x279))) = +(+(x,y),s(x279)), y = +(y,0()), +(y,z) = +(0(),+(y,z)), x = +(x,0()), +(y,z) = +(+(0(),y),z), +(x,z) = +(+(x,0()),z), s(+(x285,y)) = +(y,s(x285)), +(s(+(x287,y)),z) = +(s(x287),+(y,z)), s(+(x289,x)) = +(x,s(x289)), s(+(x291,+(y,z))) = +(+(s(x291),y),z), +(x,s(+(x293,z))) = +(+(x,s(x293)),z) PCP_in(P union P^-1,S) = We have to check termination of S: Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = 5x0 + 2x1, [0] = 5, [s](x0) = x0 + 6 orientation: +(x,0()) = 5x + 10 >= x = x +(x,s(y)) = 5x + 2y + 12 >= 5x + 2y + 6 = s(+(x,y)) +(0(),y) = 2y + 25 >= y = y +(s(x),y) = 5x + 2y + 30 >= 5x + 2y + 6 = s(+(x,y)) problem: Qed