YES Problem: b(a(),f(b(b(z,y),a()))) -> z c(c(z,x,a()),a(),y) -> f(f(c(y,a(),f(c(z,y,x))))) f(f(c(a(),y,z))) -> b(y,b(z,z)) Proof: DP Processor: DPs: c#(c(z,x,a()),a(),y) -> c#(z,y,x) c#(c(z,x,a()),a(),y) -> f#(c(z,y,x)) c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) c#(c(z,x,a()),a(),y) -> f#(c(y,a(),f(c(z,y,x)))) c#(c(z,x,a()),a(),y) -> f#(f(c(y,a(),f(c(z,y,x))))) f#(f(c(a(),y,z))) -> b#(z,z) f#(f(c(a(),y,z))) -> b#(y,b(z,z)) TRS: b(a(),f(b(b(z,y),a()))) -> z c(c(z,x,a()),a(),y) -> f(f(c(y,a(),f(c(z,y,x))))) f(f(c(a(),y,z))) -> b(y,b(z,z)) TDG Processor: DPs: c#(c(z,x,a()),a(),y) -> c#(z,y,x) c#(c(z,x,a()),a(),y) -> f#(c(z,y,x)) c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) c#(c(z,x,a()),a(),y) -> f#(c(y,a(),f(c(z,y,x)))) c#(c(z,x,a()),a(),y) -> f#(f(c(y,a(),f(c(z,y,x))))) f#(f(c(a(),y,z))) -> b#(z,z) f#(f(c(a(),y,z))) -> b#(y,b(z,z)) TRS: b(a(),f(b(b(z,y),a()))) -> z c(c(z,x,a()),a(),y) -> f(f(c(y,a(),f(c(z,y,x))))) f(f(c(a(),y,z))) -> b(y,b(z,z)) graph: c#(c(z,x,a()),a(),y) -> f#(c(z,y,x)) -> f#(f(c(a(),y,z))) -> b#(y,b(z,z)) c#(c(z,x,a()),a(),y) -> f#(c(z,y,x)) -> f#(f(c(a(),y,z))) -> b#(z,z) c#(c(z,x,a()),a(),y) -> f#(c(y,a(),f(c(z,y,x)))) -> f#(f(c(a(),y,z))) -> b#(y,b(z,z)) c#(c(z,x,a()),a(),y) -> f#(c(y,a(),f(c(z,y,x)))) -> f#(f(c(a(),y,z))) -> b#(z,z) c#(c(z,x,a()),a(),y) -> f#(f(c(y,a(),f(c(z,y,x))))) -> f#(f(c(a(),y,z))) -> b#(y,b(z,z)) c#(c(z,x,a()),a(),y) -> f#(f(c(y,a(),f(c(z,y,x))))) -> f#(f(c(a(),y,z))) -> b#(z,z) c#(c(z,x,a()),a(),y) -> c#(z,y,x) -> c#(c(z,x,a()),a(),y) -> f#(f(c(y,a(),f(c(z,y,x))))) c#(c(z,x,a()),a(),y) -> c#(z,y,x) -> c#(c(z,x,a()),a(),y) -> f#(c(y,a(),f(c(z,y,x)))) c#(c(z,x,a()),a(),y) -> c#(z,y,x) -> c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) c#(c(z,x,a()),a(),y) -> c#(z,y,x) -> c#(c(z,x,a()),a(),y) -> f#(c(z,y,x)) c#(c(z,x,a()),a(),y) -> c#(z,y,x) -> c#(c(z,x,a()),a(),y) -> c#(z,y,x) c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) -> c#(c(z,x,a()),a(),y) -> f#(f(c(y,a(),f(c(z,y,x))))) c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) -> c#(c(z,x,a()),a(),y) -> f#(c(y,a(),f(c(z,y,x)))) c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) -> c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) -> c#(c(z,x,a()),a(),y) -> f#(c(z,y,x)) c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) -> c#(c(z,x,a()),a(),y) -> c#(z,y,x) SCC Processor: #sccs: 1 #rules: 2 #arcs: 16/49 DPs: c#(c(z,x,a()),a(),y) -> c#(z,y,x) c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) TRS: b(a(),f(b(b(z,y),a()))) -> z c(c(z,x,a()),a(),y) -> f(f(c(y,a(),f(c(z,y,x))))) f(f(c(a(),y,z))) -> b(y,b(z,z)) Arctic Interpretation Processor: dimension: 2 usable rules: b(a(),f(b(b(z,y),a()))) -> z c(c(z,x,a()),a(),y) -> f(f(c(y,a(),f(c(z,y,x))))) f(f(c(a(),y,z))) -> b(y,b(z,z)) interpretation: [c#](x0, x1, x2) = [-& 2 ]x0 + [0 0]x1 + [2 2]x2, [0 0] [0 0] [0 0] [-&] [c](x0, x1, x2) = [0 1]x0 + [1 1]x1 + [0 1]x2 + [1 ], [0 -&] [-&] [f](x0) = [0 -&]x0 + [1 ], [0 0] [0 0] [0] [b](x0, x1) = [0 0]x0 + [0 0]x1 + [0], [0] [a] = [0] orientation: c#(c(z,x,a()),a(),y) = [3 3]x + [2 2]y + [2 3]z + [3] >= [2 2]x + [0 0]y + [-& 2 ]z = c#(z,y,x) c#(c(z,x,a()),a(),y) = [3 3]x + [2 2]y + [2 3]z + [3] >= [2 2]x + [2 2]y + [2 2]z + [3] = c#(y,a(),f(c(z,y,x))) [0 0] [0 0] [1] b(a(),f(b(b(z,y),a()))) = [0 0]y + [0 0]z + [1] >= z = z [1 1] [0 0] [0 1] [1] [0 0] [0 0] [0 0] [1] c(c(z,x,a()),a(),y) = [2 2]x + [0 1]y + [1 2]z + [2] >= [0 0]x + [0 0]y + [0 0]z + [1] = f(f(c(y,a(),f(c(z,y,x))))) [0 0] [0 0] [0] [0 0] [0 0] [0] f(f(c(a(),y,z))) = [0 0]y + [0 0]z + [1] >= [0 0]y + [0 0]z + [0] = b(y,b(z,z)) problem: DPs: c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) TRS: b(a(),f(b(b(z,y),a()))) -> z c(c(z,x,a()),a(),y) -> f(f(c(y,a(),f(c(z,y,x))))) f(f(c(a(),y,z))) -> b(y,b(z,z)) Restore Modifier: DPs: c#(c(z,x,a()),a(),y) -> c#(y,a(),f(c(z,y,x))) TRS: b(a(),f(b(b(z,y),a()))) -> z c(c(z,x,a()),a(),y) -> f(f(c(y,a(),f(c(z,y,x))))) f(f(c(a(),y,z))) -> b(y,b(z,z)) Bounds Processor: bound: 2 enrichment: top-dp automaton: final states: {7} transitions: b1(12,12) -> 21* b1(13,21) -> 11* f0(6) -> 6* b0(6,6) -> 6* c{#,1}(6,13,12) -> 7* a1() -> 13* f1(20) -> 17* f1(17) -> 18* f1(19) -> 20* f1(11) -> 12* f1(18) -> 11* c1(6,6,6) -> 11* c1(12,13,15) -> 19* c1(6,13,12) -> 17* c{#,2}(12,16,15) -> 7* a2() -> 16* c{#,0}(6,6,6) -> 7* f2(14) -> 15* c0(6,6,6) -> 6* c2(6,12,6) -> 14* a0() -> 6* problem: DPs: TRS: b(a(),f(b(b(z,y),a()))) -> z c(c(z,x,a()),a(),y) -> f(f(c(y,a(),f(c(z,y,x))))) f(f(c(a(),y,z))) -> b(y,b(z,z)) Qed