YES We show the termination of the TRS R: b(b(y,z),c(a(),a(),a())) -> f(c(z,y,z)) f(b(b(a(),z),c(a(),x,y))) -> z c(y,x,f(z)) -> b(f(b(z,x)),z) -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: b#(b(y,z),c(a(),a(),a())) -> f#(c(z,y,z)) p2: b#(b(y,z),c(a(),a(),a())) -> c#(z,y,z) p3: c#(y,x,f(z)) -> b#(f(b(z,x)),z) p4: c#(y,x,f(z)) -> f#(b(z,x)) p5: c#(y,x,f(z)) -> b#(z,x) and R consists of: r1: b(b(y,z),c(a(),a(),a())) -> f(c(z,y,z)) r2: f(b(b(a(),z),c(a(),x,y))) -> z r3: c(y,x,f(z)) -> b(f(b(z,x)),z) The estimated dependency graph contains the following SCCs: {p2, p3, p5} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: b#(b(y,z),c(a(),a(),a())) -> c#(z,y,z) p2: c#(y,x,f(z)) -> b#(z,x) p3: c#(y,x,f(z)) -> b#(f(b(z,x)),z) and R consists of: r1: b(b(y,z),c(a(),a(),a())) -> f(c(z,y,z)) r2: f(b(b(a(),z),c(a(),x,y))) -> z r3: c(y,x,f(z)) -> b(f(b(z,x)),z) The set of usable rules consists of r1, r2, r3 Take the reduction pair: lexicographic combination of reduction pairs: 1. max/plus interpretations on natural numbers: b#_A(x1,x2) = max{1, x1 - 5, x2 - 12} b_A(x1,x2) = max{x1 + 10, x2 + 12} c_A(x1,x2,x3) = max{x1 + 7, x2 + 19, x3 + 21} a_A = 6 c#_A(x1,x2,x3) = max{x1 + 6, x2 + 4, x3 + 6} f_A(x1) = max{23, x1 - 4} 2. max/plus interpretations on natural numbers: b#_A(x1,x2) = 1 b_A(x1,x2) = 1 c_A(x1,x2,x3) = 0 a_A = 0 c#_A(x1,x2,x3) = 0 f_A(x1) = 0 The next rules are strictly ordered: p1, p2, p3 We remove them from the problem. Then no dependency pair remains.