YES Problem: +(0(),y) -> y +(x,0()) -> x +(s(x),y) -> s(+(x,y)) +(x,s(y)) -> +(s(y),x) +(x,+(y,z)) -> +(+(x,y),z) +(x,y) -> +(y,x) Proof: AT confluence processor Complete TRS T' of input TRS: +(0(),y) -> y +(x,0()) -> x +(s(x),y) -> s(+(x,y)) +(y,s(x)) -> s(+(y,x)) +(x,s(y)) -> +(s(y),x) +(x,+(y,z)) -> +(+(x,y),z) +(x,y) -> +(y,x) T' = (P union S) with TRS P:+(x,s(y)) -> +(s(y),x) +(x,+(y,z)) -> +(+(x,y),z) +(x,y) -> +(y,x) TRS S:+(0(),y) -> y +(x,0()) -> x +(s(x),y) -> s(+(x,y)) +(y,s(x)) -> s(+(y,x)) S is linear and P is reversible. CP(S,S) = 0() = 0(), s(x) = s(+(0(),x)), s(x) = s(+(x,0())), s(+(x480,0())) = s(x480), s(+(x482,s(x))) = s(+(s(x482),x)), s(+(0(),x485)) = s(x485), s(+(s(x),x487)) = s(+(x,s(x487))) CP(S,P union P^-1) = s(y) = +(s(y),0()), +(y,z) = +(+(0(),y),z), +(x,z) = +(+(x,0()),z), y = +(y,0()), +(y,z) = +(0(),+(y,z)), x = +(x,0()), +(x,y) = +(+(x,y),0()), x = +(0(),x), s(y) = +(0(),s(y)), +(x,y) = +(x,+(y,0())), +(x,z) = +(x,+(0(),z)), y = +(0(),y), s(+(x560,s(y))) = +(s(y),s(x560)), s(+(x562,+(y,z))) = +(+(s(x562),y),z), +(x,s(+(x564,z))) = +(+(x,s(x564)),z), s(+(x566,y)) = +(y,s(x566)), s(+(y,x)) = +(x,s(y)), +(s(+(x570,y)),z) = +(s(x570),+(y,z)), s(+(x572,x)) = +(x,s(x572)), s(+(x,y)) = +(s(y),x), +(x,s(+(y,x577))) = +(+(x,y),s(x577)), s(+(x,x579)) = +(s(x579),x), s(+(s(y),x581)) = +(s(x581),s(y)), s(+(+(x,y),x583)) = +(x,+(y,s(x583))), +(s(+(x,x585)),z) = +(x,+(s(x585),z)), s(+(y,x587)) = +(s(x587),y) CP(P union P^-1,S) = +(s(x701),0()) = s(x701), +(s(x703),s(x)) = s(+(x,s(x703))), +(s(x),y) = s(+(y,x)), +(+(0(),x707),x708) = +(x707,x708), +(+(s(x),x710),x711) = s(+(x,+(x710,x711))), +(y,0()) = y, +(0(),x) = x, +(y,s(x)) = s(+(x,y)), +(0(),s(x720)) = s(x720), +(s(x),s(x724)) = s(+(s(x724),x)), +(x726,+(x727,0())) = +(x726,x727), +(x729,+(x730,s(x))) = s(+(+(x729,x730),x)) We have to check termination of S: Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = 2x0 + x1 + 2, [0] = 2, [s](x0) = x0 + 2 orientation: +(0(),y) = y + 6 >= y = y +(x,0()) = 2x + 4 >= x = x +(s(x),y) = 2x + y + 6 >= 2x + y + 4 = s(+(x,y)) +(y,s(x)) = x + 2y + 4 >= x + 2y + 4 = s(+(y,x)) problem: +(y,s(x)) -> s(+(y,x)) Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = x0 + 4x1 + 7, [s](x0) = x0 + 1 orientation: +(y,s(x)) = 4x + y + 11 >= 4x + y + 8 = s(+(y,x)) problem: Qed