YES Problem: 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) Proof: DP Processor: DPs: b#(b(y,z),c(a(),a(),a())) -> c#(z,y,z) b#(b(y,z),c(a(),a(),a())) -> f#(c(z,y,z)) c#(y,x,f(z)) -> b#(z,x) c#(y,x,f(z)) -> f#(b(z,x)) c#(y,x,f(z)) -> b#(f(b(z,x)),z) TRS: 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) Matrix Interpretation Processor: dim=2 interpretation: [f#](x0) = [0], [c#](x0, x1, x2) = [2 0]x0 + [2 0]x1 + [2 3]x2 + [1], [b#](x0, x1) = [2 0]x0 + [2 0]x1, [0 1] [f](x0) = [2 0]x0, [0 0] [2 2] [c](x0, x1, x2) = [1 0]x1 + [0 2]x2, [1] [a] = [0], [1 0] [2 2] [b](x0, x1) = [2 0]x0 + [0 0]x1 orientation: b#(b(y,z),c(a(),a(),a())) = [2 0]y + [4 4]z + [4] >= [2 0]y + [4 3]z + [1] = c#(z,y,z) b#(b(y,z),c(a(),a(),a())) = [2 0]y + [4 4]z + [4] >= [0] = f#(c(z,y,z)) c#(y,x,f(z)) = [2 0]x + [2 0]y + [6 2]z + [1] >= [2 0]x + [2 0]z = b#(z,x) c#(y,x,f(z)) = [2 0]x + [2 0]y + [6 2]z + [1] >= [0] = f#(b(z,x)) c#(y,x,f(z)) = [2 0]x + [2 0]y + [6 2]z + [1] >= [6 0]z = b#(f(b(z,x)),z) [1 0] [2 2] [6] [1 0] [0 2] b(b(y,z),c(a(),a(),a())) = [2 0]y + [4 4]z + [0] >= [0 0]y + [4 4]z = f(c(z,y,z)) [0 0] [0 0 ] [4 4] [2] f(b(b(a(),z),c(a(),x,y))) = [4 0]x + [8 16]y + [4 4]z + [2] >= z = z [0 0] [4 2] [4 2] c(y,x,f(z)) = [1 0]x + [4 0]z >= [4 0]z = b(f(b(z,x)),z) problem: DPs: TRS: 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) Qed