YES Problem: +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) d(0()) -> 0() d(s(x)) -> s(s(d(x))) f(0()) -> 0() f(s(x)) -> +(+(s(x),s(x)),s(x)) f(g(0())) -> +(+(g(0()),g(0())),g(0())) g(x) -> s(d(x)) Proof: Church Rosser Transformation Processor (to relative problem): strict: +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) d(0()) -> 0() d(s(x)) -> s(s(d(x))) f(0()) -> 0() f(s(x)) -> +(+(s(x),s(x)),s(x)) f(g(0())) -> +(+(g(0()),g(0())),g(0())) g(x) -> s(d(x)) weak: original problem: +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) d(0()) -> 0() d(s(x)) -> s(s(d(x))) f(0()) -> 0() f(s(x)) -> +(+(s(x),s(x)),s(x)) f(g(0())) -> +(+(g(0()),g(0())),g(0())) g(x) -> s(d(x)) critical peaks: LPO Processor: precedence: g > f > d ~ + > s ~ 0 problem: strict: weak: original problem: +(x,0()) -> x +(x,s(y)) -> s(+(x,y)) d(0()) -> 0() d(s(x)) -> s(s(d(x))) f(0()) -> 0() f(s(x)) -> +(+(s(x),s(x)),s(x)) f(g(0())) -> +(+(g(0()),g(0())),g(0())) g(x) -> s(d(x)) KH confluence processor Split input TRS into two TRSs S and T: TRS S: +(x,0()) -> x TRS T: +(x,s(y)) -> s(+(x,y)) d(0()) -> 0() d(s(x)) -> s(s(d(x))) f(0()) -> 0() f(s(x)) -> +(+(s(x),s(x)),s(x)) f(g(0())) -> +(+(g(0()),g(0())),g(0())) g(x) -> s(d(x)) As established above, T/S is terminating. T is strongly non-overlapping on S and S is strongly non-overlapping on T We get the following critical pairs, which are also S-critical pairs: f(s(d(0()))) = +(+(g(0()),g(0())),g(0())) all these critical pairs are joinable with S union T. Please install theorem prover 'Prover9' and 'Mace4' for handling more TRSs. All S-critical pairs are joinable. We have to check confluence of S. Church Rosser Transformation Processor (kb): +(x,0()) -> x critical peaks: joinable Matrix Interpretation Processor: dim=1 interpretation: [+](x0, x1) = x0 + x1 + 4, [0] = 0 orientation: +(x,0()) = x + 4 >= x = x problem: Qed