YES Problem: +(x,y) -> +(y,x) +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) +(0(),y) -> y +(s(x),y) -> s(+(x,y)) +(+(x,y),z) -> +(x,+(y,z)) s(x) -> s(s(x)) s(s(x)) -> s(x) 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)) s(x) -> s(s(x)) s(s(x)) -> s(x) T' = (P union S) with TRS P:+(x,y) -> +(y,x) +(+(x,y),z) -> +(x,+(y,z)) s(x) -> s(s(x)) s(s(x)) -> s(x) TRS S:+(x,0()) -> x +(x,s(y)) -> s(+(x,y)) +(0(),y) -> y +(s(x),y) -> s(+(x,y)) S is linear and P is reversible. CP(S,S) = 0() = 0(), s(x) = s(+(x,0())), s(+(0(),x364)) = s(x364), s(+(s(x),x366)) = s(+(x,s(x366))), s(y) = s(+(0(),y)), s(+(x369,0())) = s(x369), s(+(x371,s(y))) = s(+(s(x371),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,x433)) = +(s(x433),x), s(+(+(x,y),x435)) = +(x,+(y,s(x435))), +(s(+(x,x437)),z) = +(x,+(s(x437),z)), s(+(y,x439)) = +(s(x439),y), +(x,s(+(y,x441))) = +(+(x,y),s(x441)), y = +(y,0()), +(y,z) = +(0(),+(y,z)), x = +(x,0()), +(y,z) = +(+(0(),y),z), +(x,z) = +(+(x,0()),z), s(+(x447,y)) = +(y,s(x447)), +(s(+(x449,y)),z) = +(s(x449),+(y,z)), s(+(x451,x)) = +(x,s(x451)), s(+(x453,+(y,z))) = +(+(s(x453),y),z), +(x,s(+(x455,z))) = +(+(x,s(x455)),z) CP(P union P^-1,S) = +(0(),x) = x, +(s(y),x) = s(+(x,y)), +(y,0()) = y, +(y,s(x)) = s(+(x,y)), +(x561,+(x562,0())) = +(x561,x562), +(x564,+(x565,s(y))) = s(+(+(x564,x565),y)), +(x,s(s(y))) = s(+(x,y)), +(s(s(x)),y) = s(+(x,y)), +(x,s(x569)) = s(+(x,s(x569))), +(s(x570),y) = s(+(s(x570),y)), +(+(0(),x580),x581) = +(x580,x581), +(+(s(x),x583),x584) = s(+(x,+(x583,x584))) We have to check termination of S: Matrix Interpretation Processor: dim=1 interpretation: [0] = 5, [+](x0, x1) = 5x0 + 2x1, [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