YES Problem: b(f(b(x,z)),y) -> f(f(f(b(z,b(y,z))))) c(f(f(c(x,a(),z))),a(),y) -> b(y,f(b(a(),z))) b(b(c(b(a(),a()),a(),z),f(a())),y) -> z Proof: DP Processor: DPs: b#(f(b(x,z)),y) -> b#(y,z) b#(f(b(x,z)),y) -> b#(z,b(y,z)) c#(f(f(c(x,a(),z))),a(),y) -> b#(a(),z) c#(f(f(c(x,a(),z))),a(),y) -> b#(y,f(b(a(),z))) TRS: b(f(b(x,z)),y) -> f(f(f(b(z,b(y,z))))) c(f(f(c(x,a(),z))),a(),y) -> b(y,f(b(a(),z))) b(b(c(b(a(),a()),a(),z),f(a())),y) -> z TDG Processor: DPs: b#(f(b(x,z)),y) -> b#(y,z) b#(f(b(x,z)),y) -> b#(z,b(y,z)) c#(f(f(c(x,a(),z))),a(),y) -> b#(a(),z) c#(f(f(c(x,a(),z))),a(),y) -> b#(y,f(b(a(),z))) TRS: b(f(b(x,z)),y) -> f(f(f(b(z,b(y,z))))) c(f(f(c(x,a(),z))),a(),y) -> b(y,f(b(a(),z))) b(b(c(b(a(),a()),a(),z),f(a())),y) -> z graph: c#(f(f(c(x,a(),z))),a(),y) -> b#(a(),z) -> b#(f(b(x,z)),y) -> b#(z,b(y,z)) c#(f(f(c(x,a(),z))),a(),y) -> b#(a(),z) -> b#(f(b(x,z)),y) -> b#(y,z) c#(f(f(c(x,a(),z))),a(),y) -> b#(y,f(b(a(),z))) -> b#(f(b(x,z)),y) -> b#(z,b(y,z)) c#(f(f(c(x,a(),z))),a(),y) -> b#(y,f(b(a(),z))) -> b#(f(b(x,z)),y) -> b#(y,z) b#(f(b(x,z)),y) -> b#(z,b(y,z)) -> b#(f(b(x,z)),y) -> b#(z,b(y,z)) b#(f(b(x,z)),y) -> b#(z,b(y,z)) -> b#(f(b(x,z)),y) -> b#(y,z) b#(f(b(x,z)),y) -> b#(y,z) -> b#(f(b(x,z)),y) -> b#(z,b(y,z)) b#(f(b(x,z)),y) -> b#(y,z) -> b#(f(b(x,z)),y) -> b#(y,z) SCC Processor: #sccs: 1 #rules: 2 #arcs: 8/16 DPs: b#(f(b(x,z)),y) -> b#(y,z) b#(f(b(x,z)),y) -> b#(z,b(y,z)) TRS: b(f(b(x,z)),y) -> f(f(f(b(z,b(y,z))))) c(f(f(c(x,a(),z))),a(),y) -> b(y,f(b(a(),z))) b(b(c(b(a(),a()),a(),z),f(a())),y) -> z Usable Rule Processor: DPs: b#(f(b(x,z)),y) -> b#(y,z) b#(f(b(x,z)),y) -> b#(z,b(y,z)) TRS: b(f(b(x,z)),y) -> f(f(f(b(z,b(y,z))))) b(b(c(b(a(),a()),a(),z),f(a())),y) -> z Arctic Interpretation Processor: dimension: 2 usable rules: b(f(b(x,z)),y) -> f(f(f(b(z,b(y,z))))) b(b(c(b(a(),a()),a(),z),f(a())),y) -> z interpretation: [b#](x0, x1) = [-& 0 ]x0 + [1 1]x1, [1 -&] [0 0] [1 1 ] [0 ] [c](x0, x1, x2) = [-& -&]x0 + [1 0]x1 + [-& 0 ]x2 + [-&], [1 ] [a] = [-&], [-& -&] [0] [f](x0) = [2 -&]x0 + [0], [-& 0 ] [0 0 ] [0] [b](x0, x1) = [0 0 ]x0 + [0 -&]x1 + [1] orientation: b#(f(b(x,z)),y) = [-& 2 ]x + [1 1]y + [2 2]z + [2] >= [-& 0 ]y + [1 1]z = b#(y,z) b#(f(b(x,z)),y) = [-& 2 ]x + [1 1]y + [2 2]z + [2] >= [1 1]y + [1 1]z + [2] = b#(z,b(y,z)) [-& 2 ] [0 0 ] [2 2] [2] [0] b(f(b(x,z)),y) = [-& 2 ]x + [0 -&]y + [2 2]z + [2] >= [2] = f(f(f(b(z,b(y,z))))) [0 0 ] [1 1] [2] b(b(c(b(a(),a()),a(),z),f(a())),y) = [0 -&]y + [1 1]z + [3] >= z = z problem: DPs: b#(f(b(x,z)),y) -> b#(z,b(y,z)) TRS: b(f(b(x,z)),y) -> f(f(f(b(z,b(y,z))))) b(b(c(b(a(),a()),a(),z),f(a())),y) -> z Restore Modifier: DPs: b#(f(b(x,z)),y) -> b#(z,b(y,z)) TRS: b(f(b(x,z)),y) -> f(f(f(b(z,b(y,z))))) c(f(f(c(x,a(),z))),a(),y) -> b(y,f(b(a(),z))) b(b(c(b(a(),a()),a(),z),f(a())),y) -> z Subterm Criterion Processor: simple projection: pi(b#) = 0 problem: DPs: TRS: b(f(b(x,z)),y) -> f(f(f(b(z,b(y,z))))) c(f(f(c(x,a(),z))),a(),y) -> b(y,f(b(a(),z))) b(b(c(b(a(),a()),a(),z),f(a())),y) -> z Qed