YES Problem: b(a(),b(c(z,x,y),a())) -> b(b(z,c(y,z,a())),x) f(c(a(),b(b(z,a()),y),x)) -> f(c(x,b(z,x),y)) c(f(c(a(),y,a())),x,z) -> f(b(b(z,z),f(b(y,b(x,a()))))) Proof: DP Processor: DPs: b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) b#(a(),b(c(z,x,y),a())) -> b#(z,c(y,z,a())) b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) f#(c(a(),b(b(z,a()),y),x)) -> b#(z,x) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) f#(c(a(),b(b(z,a()),y),x)) -> f#(c(x,b(z,x),y)) c#(f(c(a(),y,a())),x,z) -> b#(x,a()) c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) c#(f(c(a(),y,a())),x,z) -> f#(b(y,b(x,a()))) c#(f(c(a(),y,a())),x,z) -> b#(z,z) c#(f(c(a(),y,a())),x,z) -> b#(b(z,z),f(b(y,b(x,a())))) c#(f(c(a(),y,a())),x,z) -> f#(b(b(z,z),f(b(y,b(x,a()))))) TRS: b(a(),b(c(z,x,y),a())) -> b(b(z,c(y,z,a())),x) f(c(a(),b(b(z,a()),y),x)) -> f(c(x,b(z,x),y)) c(f(c(a(),y,a())),x,z) -> f(b(b(z,z),f(b(y,b(x,a()))))) Matrix Interpretation Processor: dim=2 usable rules: b(a(),b(c(z,x,y),a())) -> b(b(z,c(y,z,a())),x) f(c(a(),b(b(z,a()),y),x)) -> f(c(x,b(z,x),y)) c(f(c(a(),y,a())),x,z) -> f(b(b(z,z),f(b(y,b(x,a()))))) interpretation: [f#](x0) = [0 1]x0, [c#](x0, x1, x2) = [1 0]x1 + [1 0]x2 + [2], [b#](x0, x1) = [1 0]x1, [0] [f](x0) = [0], [1 0] [1 0] [1] [b](x0, x1) = [0 0]x0 + [0 0]x1 + [1], [3 0] [2 0] [3 0] [3] [c](x0, x1, x2) = [0 0]x0 + [1 1]x1 + [1 0]x2 + [1], [0] [a] = [0] orientation: b#(a(),b(c(z,x,y),a())) = [2 0]x + [3 0]y + [3 0]z + [4] >= [1 0]z + [2] = c#(y,z,a()) b#(a(),b(c(z,x,y),a())) = [2 0]x + [3 0]y + [3 0]z + [4] >= [3 0]y + [2 0]z + [3] = b#(z,c(y,z,a())) b#(a(),b(c(z,x,y),a())) = [2 0]x + [3 0]y + [3 0]z + [4] >= [1 0]x = b#(b(z,c(y,z,a())),x) f#(c(a(),b(b(z,a()),y),x)) = [1 0]x + [1 0]y + [1 0]z + [4] >= [1 0]x = b#(z,x) f#(c(a(),b(b(z,a()),y),x)) = [1 0]x + [1 0]y + [1 0]z + [4] >= [1 0]x + [1 0]y + [1 0]z + [3] = c#(x,b(z,x),y) f#(c(a(),b(b(z,a()),y),x)) = [1 0]x + [1 0]y + [1 0]z + [4] >= [1 0]x + [1 0]y + [1 0]z + [3] = f#(c(x,b(z,x),y)) c#(f(c(a(),y,a())),x,z) = [1 0]x + [1 0]z + [2] >= [0] = b#(x,a()) c#(f(c(a(),y,a())),x,z) = [1 0]x + [1 0]z + [2] >= [1 0]x + [1] = b#(y,b(x,a())) c#(f(c(a(),y,a())),x,z) = [1 0]x + [1 0]z + [2] >= [1] = f#(b(y,b(x,a()))) c#(f(c(a(),y,a())),x,z) = [1 0]x + [1 0]z + [2] >= [1 0]z = b#(z,z) c#(f(c(a(),y,a())),x,z) = [1 0]x + [1 0]z + [2] >= [0] = b#(b(z,z),f(b(y,b(x,a())))) c#(f(c(a(),y,a())),x,z) = [1 0]x + [1 0]z + [2] >= [1] = f#(b(b(z,z),f(b(y,b(x,a()))))) [2 0] [3 0] [3 0] [5] [1 0] [3 0] [3 0] [5] b(a(),b(c(z,x,y),a())) = [0 0]x + [0 0]y + [0 0]z + [1] >= [0 0]x + [0 0]y + [0 0]z + [1] = b(b(z,c(y,z,a())),x) [0] [0] f(c(a(),b(b(z,a()),y),x)) = [0] >= [0] = f(c(x,b(z,x),y)) [2 0] [3 0] [3] [0] c(f(c(a(),y,a())),x,z) = [1 1]x + [1 0]z + [1] >= [0] = f(b(b(z,z),f(b(y,b(x,a()))))) problem: DPs: TRS: b(a(),b(c(z,x,y),a())) -> b(b(z,c(y,z,a())),x) f(c(a(),b(b(z,a()),y),x)) -> f(c(x,b(z,x),y)) c(f(c(a(),y,a())),x,z) -> f(b(b(z,z),f(b(y,b(x,a()))))) Qed