YES Problem: a() -> b() a() -> c() a() -> e() b() -> d() c() -> a() d() -> a() d() -> e() g(x) -> h(a()) h(x) -> e() Proof: AT confluence processor Complete TRS T' of input TRS: a() -> e() d() -> e() g(x) -> h(a()) h(x) -> e() b() -> e() c() -> e() a() -> b() a() -> c() b() -> d() c() -> a() d() -> a() T' = (P union S) with TRS P:a() -> b() a() -> c() b() -> d() c() -> a() d() -> a() TRS S:a() -> e() d() -> e() g(x) -> h(a()) h(x) -> e() b() -> e() c() -> e() S is linear and P is reversible. CP(S,S) = CP(S,P union P^-1) = e() = b(), e() = c(), e() = d(), e() = a() CP(P union P^-1,S) = b() = e(), c() = e(), d() = e(), a() = e() We have to check termination of S: Matrix Interpretation Processor: dim=1 interpretation: [d] = 0, [b] = 0, [e] = 0, [g](x0) = 4x0 + 6, [a] = 4, [h](x0) = x0 + 2, [c] = 4 orientation: a() = 4 >= 0 = e() d() = 0 >= 0 = e() g(x) = 4x + 6 >= 6 = h(a()) h(x) = x + 2 >= 0 = e() b() = 0 >= 0 = e() c() = 4 >= 0 = e() problem: d() -> e() g(x) -> h(a()) b() -> e() Matrix Interpretation Processor: dim=1 interpretation: [d] = 4, [b] = 0, [e] = 0, [g](x0) = 2x0 + 6, [a] = 4, [h](x0) = x0 + 1 orientation: d() = 4 >= 0 = e() g(x) = 2x + 6 >= 5 = h(a()) b() = 0 >= 0 = e() problem: b() -> e() Matrix Interpretation Processor: dim=1 interpretation: [b] = 1, [e] = 0 orientation: b() = 1 >= 0 = e() problem: Qed