YES Problem: +(0(),y) -> y +(s(x),y) -> s(+(x,y)) inc(x) -> s(x) +(x,y) -> +(y,x) inc(+(x,y)) -> +(inc(x),y) Proof: AT confluence processor Complete TRS T' of input TRS: +(0(),y) -> y +(s(x),y) -> s(+(x,y)) inc(x) -> s(x) inc(+(x,y)) -> +(inc(x),y) +(y,0()) -> y +(y,s(x)) -> s(+(y,x)) +(x,y) -> +(y,x) T' = (P union S) with TRS P:+(x,y) -> +(y,x) TRS S:+(0(),y) -> y +(s(x),y) -> s(+(x,y)) inc(x) -> s(x) inc(+(x,y)) -> +(inc(x),y) +(y,0()) -> y +(y,s(x)) -> s(+(y,x)) S is linear and P is reversible. CP(S,S) = inc(y) = +(inc(0()),y), 0() = 0(), s(x) = s(+(0(),x)), inc(s(+(x358,y))) = +(inc(s(x358)),y), s(+(x360,0())) = s(x360), s(+(x362,s(x))) = s(+(s(x362),x)), s(+(x,y)) = +(inc(x),y), +(inc(x365),x366) = s(+(x365,x366)), s(x) = s(+(x,0())), inc(x) = +(inc(x),0()), s(+(0(),x371)) = s(x371), s(+(s(x),x373)) = s(+(x,s(x373))), inc(s(+(x,x375))) = +(inc(x),s(x375)) CP(S,P union P^-1) = y = +(y,0()), x = +(x,0()), s(+(x396,y)) = +(y,s(x396)), s(+(x398,x)) = +(x,s(x398)), x = +(0(),x), y = +(0(),y), s(+(x,x403)) = +(s(x403),x), s(+(y,x405)) = +(s(x405),y) CP(P union P^-1,S) = +(y,0()) = y, +(y,s(x)) = s(+(x,y)), inc(+(y,x)) = +(inc(x),y), +(0(),y) = y, +(s(x),y) = s(+(y,x)) We have to check termination of S: Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = 4x0 + x1 + 1, [inc](x0) = 2x0, [0] = 0, [s](x0) = x0 orientation: +(0(),y) = y + 1 >= y = y +(s(x),y) = 4x + y + 1 >= 4x + y + 1 = s(+(x,y)) inc(x) = 2x >= x = s(x) inc(+(x,y)) = 8x + 2y + 2 >= 8x + y + 1 = +(inc(x),y) +(y,0()) = 4y + 1 >= y = y +(y,s(x)) = x + 4y + 1 >= x + 4y + 1 = s(+(y,x)) problem: +(s(x),y) -> s(+(x,y)) inc(x) -> s(x) +(y,s(x)) -> s(+(y,x)) Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = x0 + 2x1 + 7, [inc](x0) = 4x0 + 2, [s](x0) = x0 + 2 orientation: +(s(x),y) = x + 2y + 9 >= x + 2y + 9 = s(+(x,y)) inc(x) = 4x + 2 >= x + 2 = s(x) +(y,s(x)) = 2x + y + 11 >= 2x + y + 9 = s(+(y,x)) problem: +(s(x),y) -> s(+(x,y)) inc(x) -> s(x) Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = x0 + x1, [inc](x0) = x0 + 1, [s](x0) = x0 orientation: +(s(x),y) = x + y >= x + y = s(+(x,y)) inc(x) = x + 1 >= x = s(x) problem: +(s(x),y) -> s(+(x,y)) Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = 4x0 + x1, [s](x0) = x0 + 5 orientation: +(s(x),y) = 4x + y + 20 >= 4x + y + 5 = s(+(x,y)) problem: Qed