YES Problem: s(p(x)) -> x p(s(x)) -> x +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) +(x,p(y)) -> p(+(x,y)) -(x,0()) -> x -(x,s(y)) -> p(-(x,y)) -(x,p(y)) -> s(-(x,y)) Proof: Church Rosser Transformation Processor (critical pair closing system, Thm 2.11): +(x201,p(x200)) -> p(+(x201,x200)) s(p(x204)) -> x204 -(x206,p(x205)) -> s(-(x206,x205)) p(s(x209)) -> x209 +(x211,s(x210)) -> s(+(x211,x210)) -(x216,s(x215)) -> p(-(x216,x215)) critical peaks: joinable Matrix Interpretation Processor: dim=1 interpretation: [-](x0, x1) = 4x0 + 2x1 + 2, [s](x0) = x0 + 2, [+](x0, x1) = x0 + x1 + 3, [p](x0) = x0 + 1 orientation: +(x201,p(x200)) = x200 + x201 + 4 >= x200 + x201 + 4 = p(+(x201,x200)) s(p(x204)) = x204 + 3 >= x204 = x204 -(x206,p(x205)) = 2x205 + 4x206 + 4 >= 2x205 + 4x206 + 4 = s(-(x206,x205)) p(s(x209)) = x209 + 3 >= x209 = x209 +(x211,s(x210)) = x210 + x211 + 5 >= x210 + x211 + 5 = s(+(x211,x210)) -(x216,s(x215)) = 2x215 + 4x216 + 6 >= 2x215 + 4x216 + 3 = p(-(x216,x215)) problem: +(x201,p(x200)) -> p(+(x201,x200)) -(x206,p(x205)) -> s(-(x206,x205)) +(x211,s(x210)) -> s(+(x211,x210)) Matrix Interpretation Processor: dim=1 interpretation: [-](x0, x1) = 2x0 + x1 + 2, [s](x0) = x0, [+](x0, x1) = x0 + 4x1 + 4, [p](x0) = x0 + 4 orientation: +(x201,p(x200)) = 4x200 + x201 + 20 >= 4x200 + x201 + 8 = p(+(x201,x200)) -(x206,p(x205)) = x205 + 2x206 + 6 >= x205 + 2x206 + 2 = s(-(x206,x205)) +(x211,s(x210)) = 4x210 + x211 + 4 >= 4x210 + x211 + 4 = s(+(x211,x210)) problem: +(x211,s(x210)) -> s(+(x211,x210)) Matrix Interpretation Processor: dim=1 interpretation: [s](x0) = x0 + 1, [+](x0, x1) = x0 + 4x1 + 7 orientation: +(x211,s(x210)) = 4x210 + x211 + 11 >= 4x210 + x211 + 8 = s(+(x211,x210)) problem: Qed