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()))))) TDG 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()))))) graph: f#(c(a(),b(b(z,a()),y),x)) -> f#(c(x,b(z,x),y)) -> f#(c(a(),b(b(z,a()),y),x)) -> f#(c(x,b(z,x),y)) f#(c(a(),b(b(z,a()),y),x)) -> f#(c(x,b(z,x),y)) -> 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)) -> 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) -> c#(f(c(a(),y,a())),x,z) -> f#(b(b(z,z),f(b(y,b(x,a()))))) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> b#(b(z,z),f(b(y,b(x,a())))) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> b#(z,z) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> f#(b(y,b(x,a()))) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> b#(x,a()) f#(c(a(),b(b(z,a()),y),x)) -> b#(z,x) -> 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) -> b#(a(),b(c(z,x,y),a())) -> b#(z,c(y,z,a())) f#(c(a(),b(b(z,a()),y),x)) -> b#(z,x) -> b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) c#(f(c(a(),y,a())),x,z) -> f#(b(b(z,z),f(b(y,b(x,a()))))) -> 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()))))) -> f#(c(a(),b(b(z,a()),y),x)) -> 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()))))) -> f#(c(a(),b(b(z,a()),y),x)) -> b#(z,x) c#(f(c(a(),y,a())),x,z) -> f#(b(y,b(x,a()))) -> 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(y,b(x,a()))) -> f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) c#(f(c(a(),y,a())),x,z) -> f#(b(y,b(x,a()))) -> f#(c(a(),b(b(z,a()),y),x)) -> b#(z,x) c#(f(c(a(),y,a())),x,z) -> b#(b(z,z),f(b(y,b(x,a())))) -> b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) c#(f(c(a(),y,a())),x,z) -> b#(b(z,z),f(b(y,b(x,a())))) -> b#(a(),b(c(z,x,y),a())) -> b#(z,c(y,z,a())) c#(f(c(a(),y,a())),x,z) -> b#(b(z,z),f(b(y,b(x,a())))) -> b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) c#(f(c(a(),y,a())),x,z) -> b#(z,z) -> b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) c#(f(c(a(),y,a())),x,z) -> b#(z,z) -> b#(a(),b(c(z,x,y),a())) -> b#(z,c(y,z,a())) c#(f(c(a(),y,a())),x,z) -> b#(z,z) -> b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) -> b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) -> b#(a(),b(c(z,x,y),a())) -> b#(z,c(y,z,a())) c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) -> b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) c#(f(c(a(),y,a())),x,z) -> b#(x,a()) -> b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) c#(f(c(a(),y,a())),x,z) -> b#(x,a()) -> b#(a(),b(c(z,x,y),a())) -> b#(z,c(y,z,a())) c#(f(c(a(),y,a())),x,z) -> b#(x,a()) -> b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> f#(b(b(z,z),f(b(y,b(x,a()))))) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> b#(b(z,z),f(b(y,b(x,a())))) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> b#(z,z) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> f#(b(y,b(x,a()))) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> b#(x,a()) b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) -> b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) -> 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) -> 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) b#(a(),b(c(z,x,y),a())) -> b#(z,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#(z,c(y,z,a())) -> b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) EDG 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()))))) graph: f#(c(a(),b(b(z,a()),y),x)) -> f#(c(x,b(z,x),y)) -> f#(c(a(),b(b(z,a()),y),x)) -> b#(z,x) f#(c(a(),b(b(z,a()),y),x)) -> f#(c(x,b(z,x),y)) -> 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)) -> f#(c(a(),b(b(z,a()),y),x)) -> f#(c(x,b(z,x),y)) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> b#(x,a()) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> f#(b(y,b(x,a()))) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> b#(z,z) f#(c(a(),b(b(z,a()),y),x)) -> c#(x,b(z,x),y) -> c#(f(c(a(),y,a())),x,z) -> b#(b(z,z),f(b(y,b(x,a())))) f#(c(a(),b(b(z,a()),y),x)) -> 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()))))) f#(c(a(),b(b(z,a()),y),x)) -> b#(z,x) -> b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) f#(c(a(),b(b(z,a()),y),x)) -> b#(z,x) -> b#(a(),b(c(z,x,y),a())) -> b#(z,c(y,z,a())) f#(c(a(),b(b(z,a()),y),x)) -> b#(z,x) -> b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) -> b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) -> b#(a(),b(c(z,x,y),a())) -> b#(z,c(y,z,a())) c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) -> b#(a(),b(c(z,x,y),a())) -> b#(b(z,c(y,z,a())),x) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> b#(x,a()) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> f#(b(y,b(x,a()))) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> b#(z,z) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> b#(b(z,z),f(b(y,b(x,a())))) b#(a(),b(c(z,x,y),a())) -> c#(y,z,a()) -> c#(f(c(a(),y,a())),x,z) -> f#(b(b(z,z),f(b(y,b(x,a()))))) SCC Processor: #sccs: 2 #rules: 3 #arcs: 21/144 DPs: f#(c(a(),b(b(z,a()),y),x)) -> f#(c(x,b(z,x),y)) 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 interpretation: [f#](x0) = [1 0]x0 + [3], [0] [f](x0) = [0], [1 1] [2 0] [0] [b](x0, x1) = [1 0]x0 + [1 0]x1 + [1], [0 0] [1 1] [3 0] [1] [c](x0, x1, x2) = [3 3]x0 + [0 0]x1 + [0 0]x2 + [2], [0] [a] = [0] orientation: f#(c(a(),b(b(z,a()),y),x)) = [3 0]x + [3 0]y + [3 2]z + [6] >= [3 0]x + [3 0]y + [2 1]z + [5] = f#(c(x,b(z,x),y)) [2 2] [6 0] [6 6] [6] [2 0] [5 4] [4] b(a(),b(c(z,x,y),a())) = [1 1]x + [3 0]y + [3 3]z + [4] >= [1 0]x + [3 3]z + [3] = 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)) [1 1] [3 0] [1] [0] c(f(c(a(),y,a())),x,z) = [0 0]x + [0 0]z + [2] >= [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 DPs: c#(f(c(a(),y,a())),x,z) -> b#(y,b(x,a())) b#(a(),b(c(z,x,y),a())) -> c#(y,z,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=1 interpretation: [c#](x0, x1, x2) = 5x0 + 2x1 + 4, [b#](x0, x1) = 2x1, [f](x0) = 5, [b](x0, x1) = x0 + x1 + 6, [c](x0, x1, x2) = 3x0 + 2x1 + 3x2, [a] = 0 orientation: c#(f(c(a(),y,a())),x,z) = 2x + 29 >= 2x + 12 = b#(y,b(x,a())) b#(a(),b(c(z,x,y),a())) = 4x + 6y + 6z + 12 >= 5y + 2z + 4 = c#(y,z,a()) b(a(),b(c(z,x,y),a())) = 2x + 3y + 3z + 12 >= x + 3y + 3z + 12 = b(b(z,c(y,z,a())),x) f(c(a(),b(b(z,a()),y),x)) = 5 >= 5 = f(c(x,b(z,x),y)) c(f(c(a(),y,a())),x,z) = 2x + 3z + 15 >= 5 = 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