YES Problem: +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) +(0(),y) -> y +(s(x),y) -> s(+(x,y)) inc(x) -> s(x) +(+(x,y),z) -> +(x,+(y,z)) +(x,y) -> +(y,x) inc(+(x,y)) -> +(inc(x),y) 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)) inc(x) -> s(x) inc(+(x,y)) -> +(inc(x),y) +(+(x,y),z) -> +(x,+(y,z)) +(x,y) -> +(y,x) T' = (P union S) with TRS P:+(+(x,y),z) -> +(x,+(y,z)) +(x,y) -> +(y,x) TRS S:+(x,0()) -> x +(x,s(y)) -> s(+(x,y)) +(0(),y) -> y +(s(x),y) -> s(+(x,y)) inc(x) -> s(x) inc(+(x,y)) -> +(inc(x),y) S is linear and P is reversible. CP(S,S) = 0() = 0(), s(x) = s(+(x,0())), inc(x) = +(inc(x),0()), s(+(0(),x458)) = s(x458), s(+(s(x),x460)) = s(+(x,s(x460))), inc(s(+(x,x462))) = +(inc(x),s(x462)), s(y) = s(+(0(),y)), inc(y) = +(inc(0()),y), s(+(x466,0())) = s(x466), s(+(x468,s(y))) = s(+(s(x468),y)), inc(s(+(x470,y))) = +(inc(s(x470)),y), s(+(x,y)) = +(inc(x),y), +(inc(x473),x474) = s(+(x473,x474)) CP(S,P union P^-1) = +(x,y) = +(x,+(y,0())), +(x,z) = +(x,+(0(),z)), x = +(0(),x), +(x,y) = +(+(x,y),0()), y = +(0(),y), s(+(+(x,y),x535)) = +(x,+(y,s(x535))), +(s(+(x,x537)),z) = +(x,+(s(x537),z)), s(+(x,x539)) = +(s(x539),x), +(x,s(+(y,x541))) = +(+(x,y),s(x541)), s(+(y,x543)) = +(s(x543),y), +(y,z) = +(0(),+(y,z)), y = +(y,0()), +(y,z) = +(+(0(),y),z), +(x,z) = +(+(x,0()),z), x = +(x,0()), +(s(+(x549,y)),z) = +(s(x549),+(y,z)), s(+(x551,y)) = +(y,s(x551)), s(+(x553,+(y,z))) = +(+(s(x553),y),z), +(x,s(+(x555,z))) = +(+(x,s(x555)),z), s(+(x557,x)) = +(x,s(x557)) CP(P union P^-1,S) = +(x669,+(x670,0())) = +(x669,x670), +(x672,+(x673,s(y))) = s(+(+(x672,x673),y)), inc(+(x675,+(x676,y))) = +(inc(+(x675,x676)),y), +(0(),x) = x, +(s(y),x) = s(+(x,y)), +(y,0()) = y, +(y,s(x)) = s(+(x,y)), inc(+(y,x)) = +(inc(x),y), +(+(0(),x689),x690) = +(x689,x690), +(+(s(x),x692),x693) = s(+(x,+(x692,x693))), inc(+(+(x,x695),x696)) = +(inc(x),+(x695,x696)) We have to check termination of S: Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = x0 + x1 + 2, [inc](x0) = x0, [0] = 1, [s](x0) = x0 orientation: +(x,0()) = x + 3 >= x = x +(x,s(y)) = x + y + 2 >= x + y + 2 = s(+(x,y)) +(0(),y) = y + 3 >= y = y +(s(x),y) = x + y + 2 >= x + y + 2 = s(+(x,y)) inc(x) = x >= x = s(x) inc(+(x,y)) = x + y + 2 >= x + y + 2 = +(inc(x),y) problem: +(x,s(y)) -> s(+(x,y)) +(s(x),y) -> s(+(x,y)) inc(x) -> s(x) inc(+(x,y)) -> +(inc(x),y) Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = 4x0 + 4x1 + 4, [inc](x0) = 4x0 + 4, [s](x0) = x0 orientation: +(x,s(y)) = 4x + 4y + 4 >= 4x + 4y + 4 = s(+(x,y)) +(s(x),y) = 4x + 4y + 4 >= 4x + 4y + 4 = s(+(x,y)) inc(x) = 4x + 4 >= x = s(x) inc(+(x,y)) = 16x + 16y + 20 >= 16x + 4y + 20 = +(inc(x),y) problem: +(x,s(y)) -> s(+(x,y)) +(s(x),y) -> s(+(x,y)) inc(+(x,y)) -> +(inc(x),y) Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = 2x0 + 7x1 + 2, [inc](x0) = 3x0 + 1, [s](x0) = x0 orientation: +(x,s(y)) = 2x + 7y + 2 >= 2x + 7y + 2 = s(+(x,y)) +(s(x),y) = 2x + 7y + 2 >= 2x + 7y + 2 = s(+(x,y)) inc(+(x,y)) = 6x + 21y + 7 >= 6x + 7y + 4 = +(inc(x),y) problem: +(x,s(y)) -> s(+(x,y)) +(s(x),y) -> s(+(x,y)) Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = 2x0 + x1 + 1, [s](x0) = x0 + 1 orientation: +(x,s(y)) = 2x + y + 2 >= 2x + y + 2 = s(+(x,y)) +(s(x),y) = 2x + y + 3 >= 2x + y + 2 = s(+(x,y)) problem: +(x,s(y)) -> s(+(x,y)) Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = x0 + 4x1, [s](x0) = x0 + 5 orientation: +(x,s(y)) = x + 4y + 20 >= x + 4y + 5 = s(+(x,y)) problem: Qed