YES Problem: Q(q(x)) -> x p(p(x)) -> q(q(x)) p(Q(Q(x))) -> Q(Q(p(x))) Q(p(q(x))) -> q(p(Q(x))) q(q(p(x))) -> p(q(q(x))) q(Q(x)) -> x Proof: AT confluence processor Complete TRS T' of input TRS: Q(q(x)) -> x p(p(x)) -> q(q(x)) p(Q(Q(x))) -> Q(Q(p(x))) Q(p(q(x))) -> q(p(Q(x))) q(q(p(x))) -> p(q(q(x))) q(Q(x)) -> x T' = (P union S) with TRS P: TRS S:Q(q(x)) -> x p(p(x)) -> q(q(x)) p(Q(Q(x))) -> Q(Q(p(x))) Q(p(q(x))) -> q(p(Q(x))) q(q(p(x))) -> p(q(q(x))) q(Q(x)) -> x S is linear and P is reversible. CP(S,S) = p(Q(x193)) = Q(Q(p(q(x193)))), q(x194) = q(x194), p(q(q(x195))) = q(q(p(x195))), q(q(q(q(x196)))) = p(q(q(p(x196)))), p(Q(Q(p(x197)))) = q(q(Q(Q(x197)))), q(q(Q(Q(p(x198))))) = p(q(q(Q(Q(x198))))), p(Q(q(p(Q(x199))))) = Q(Q(p(p(q(x199))))), q(q(p(Q(x200)))) = p(q(x200)), Q(p(q(q(x201)))) = q(p(x201)), Q(p(p(q(q(x202))))) = q(p(Q(q(p(x202))))), Q(x203) = Q(x203), Q(p(x204)) = q(p(Q(Q(x204)))) CP(S,P union P^-1) = CP(P union P^-1,S) = We have to check termination of S: Matrix Interpretation Processor: dim=1 interpretation: [Q](x0) = x0 + 5, [q](x0) = x0 + 4, [p](x0) = x0 + 4 orientation: Q(q(x)) = x + 9 >= x = x p(p(x)) = x + 8 >= x + 8 = q(q(x)) p(Q(Q(x))) = x + 14 >= x + 14 = Q(Q(p(x))) Q(p(q(x))) = x + 13 >= x + 13 = q(p(Q(x))) q(q(p(x))) = x + 12 >= x + 12 = p(q(q(x))) q(Q(x)) = x + 9 >= x = x problem: p(p(x)) -> q(q(x)) p(Q(Q(x))) -> Q(Q(p(x))) Q(p(q(x))) -> q(p(Q(x))) q(q(p(x))) -> p(q(q(x))) Matrix Interpretation Processor: dim=1 interpretation: [Q](x0) = x0, [q](x0) = x0, [p](x0) = x0 + 1 orientation: p(p(x)) = x + 2 >= x = q(q(x)) p(Q(Q(x))) = x + 1 >= x + 1 = Q(Q(p(x))) Q(p(q(x))) = x + 1 >= x + 1 = q(p(Q(x))) q(q(p(x))) = x + 1 >= x + 1 = p(q(q(x))) problem: p(Q(Q(x))) -> Q(Q(p(x))) Q(p(q(x))) -> q(p(Q(x))) q(q(p(x))) -> p(q(q(x))) Matrix Interpretation Processor: dim=1 interpretation: [Q](x0) = 4x0, [q](x0) = 2x0 + 1, [p](x0) = x0 orientation: p(Q(Q(x))) = 16x >= 16x = Q(Q(p(x))) Q(p(q(x))) = 8x + 4 >= 8x + 1 = q(p(Q(x))) q(q(p(x))) = 4x + 3 >= 4x + 3 = p(q(q(x))) problem: p(Q(Q(x))) -> Q(Q(p(x))) q(q(p(x))) -> p(q(q(x))) Matrix Interpretation Processor: dim=1 interpretation: [Q](x0) = x0, [q](x0) = 2x0 + 1, [p](x0) = 2x0 + 2 orientation: p(Q(Q(x))) = 2x + 2 >= 2x + 2 = Q(Q(p(x))) q(q(p(x))) = 8x + 11 >= 8x + 8 = p(q(q(x))) problem: p(Q(Q(x))) -> Q(Q(p(x))) Matrix Interpretation Processor: dim=1 interpretation: [Q](x0) = 2x0 + 4, [p](x0) = 2x0 + 1 orientation: p(Q(Q(x))) = 8x + 25 >= 8x + 16 = Q(Q(p(x))) problem: Qed