YES Problem: f(x,f(a(),a())) -> f(f(f(a(),a()),a()),f(a(),x)) Proof: DP Processor: DPs: f#(x,f(a(),a())) -> f#(a(),x) f#(x,f(a(),a())) -> f#(f(a(),a()),a()) f#(x,f(a(),a())) -> f#(f(f(a(),a()),a()),f(a(),x)) TRS: f(x,f(a(),a())) -> f(f(f(a(),a()),a()),f(a(),x)) EDG Processor: DPs: f#(x,f(a(),a())) -> f#(a(),x) f#(x,f(a(),a())) -> f#(f(a(),a()),a()) f#(x,f(a(),a())) -> f#(f(f(a(),a()),a()),f(a(),x)) TRS: f(x,f(a(),a())) -> f(f(f(a(),a()),a()),f(a(),x)) graph: f#(x,f(a(),a())) -> f#(f(f(a(),a()),a()),f(a(),x)) -> f#(x,f(a(),a())) -> f#(a(),x) f#(x,f(a(),a())) -> f#(f(f(a(),a()),a()),f(a(),x)) -> f#(x,f(a(),a())) -> f#(f(a(),a()),a()) f#(x,f(a(),a())) -> f#(f(f(a(),a()),a()),f(a(),x)) -> f#(x,f(a(),a())) -> f#(f(f(a(),a()),a()),f(a(),x)) f#(x,f(a(),a())) -> f#(a(),x) -> f#(x,f(a(),a())) -> f#(a(),x) f#(x,f(a(),a())) -> f#(a(),x) -> f#(x,f(a(),a())) -> f#(f(a(),a()),a()) f#(x,f(a(),a())) -> f#(a(),x) -> f#(x,f(a(),a())) -> f#(f(f(a(),a()),a()),f(a(),x)) SCC Processor: #sccs: 1 #rules: 2 #arcs: 6/9 DPs: f#(x,f(a(),a())) -> f#(f(f(a(),a()),a()),f(a(),x)) f#(x,f(a(),a())) -> f#(a(),x) TRS: f(x,f(a(),a())) -> f(f(f(a(),a()),a()),f(a(),x)) Bounds Processor: bound: 1 enrichment: match-dp automaton: final states: {5} transitions: f{#,1}(17,15) -> 3* f{#,1}(17,19) -> 5* f{#,1}(14,17) -> 3* f1(17,16) -> 15* f1(14,2) -> 15* f1(14,8) -> 19* f1(14,14) -> 16* f1(16,14) -> 17* f1(17,15) -> 15* f1(14,1) -> 15* f1(14,3) -> 15* f1(14,17) -> 15* a1() -> 14* f{#,0}(3,1) -> 3* f{#,0}(3,3) -> 3* f{#,0}(1,2) -> 3* f{#,0}(1,8) -> 5* f{#,0}(2,1) -> 3* f{#,0}(2,3) -> 3* f{#,0}(3,2) -> 3* f{#,0}(8,6) -> 5* f{#,0}(1,1) -> 3* f{#,0}(1,3) -> 3* f{#,0}(2,2) -> 3* f0(3,1) -> 2* f0(3,3) -> 2* f0(1,2) -> 2* f0(1,4) -> 6* f0(7,1) -> 8* f0(2,1) -> 2* f0(2,3) -> 2* f0(3,2) -> 2* f0(1,1) -> 7,2 f0(1,3) -> 2* f0(2,2) -> 6,2 a0() -> 1* 1 -> 4* 2 -> 4* 3 -> 4* problem: DPs: f#(x,f(a(),a())) -> f#(a(),x) TRS: f(x,f(a(),a())) -> f(f(f(a(),a()),a()),f(a(),x)) Matrix Interpretation Processor: dimension: 1 interpretation: [f#](x0, x1) = x0 + x1, [f](x0, x1) = 1, [a] = 0 orientation: f#(x,f(a(),a())) = x + 1 >= x = f#(a(),x) f(x,f(a(),a())) = 1 >= 1 = f(f(f(a(),a()),a()),f(a(),x)) problem: DPs: TRS: f(x,f(a(),a())) -> f(f(f(a(),a()),a()),f(a(),x)) Qed