YES Problem: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) Proof: DP Processor: DPs: f#(f(f(a(),b()),c()),x) -> f#(b(),x) f#(f(f(a(),b()),c()),x) -> f#(c(),f(b(),x)) f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) f#(f(f(a(),b()),c()),x) -> f#(b(),f(a(),f(c(),f(b(),x)))) f#(x,f(y,z)) -> f#(x,y) f#(x,f(y,z)) -> f#(f(x,y),z) TRS: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) EDG Processor: DPs: f#(f(f(a(),b()),c()),x) -> f#(b(),x) f#(f(f(a(),b()),c()),x) -> f#(c(),f(b(),x)) f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) f#(f(f(a(),b()),c()),x) -> f#(b(),f(a(),f(c(),f(b(),x)))) f#(x,f(y,z)) -> f#(x,y) f#(x,f(y,z)) -> f#(f(x,y),z) TRS: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) graph: f#(f(f(a(),b()),c()),x) -> f#(c(),f(b(),x)) -> f#(x,f(y,z)) -> f#(x,y) f#(f(f(a(),b()),c()),x) -> f#(c(),f(b(),x)) -> f#(x,f(y,z)) -> f#(f(x,y),z) f#(f(f(a(),b()),c()),x) -> f#(b(),f(a(),f(c(),f(b(),x)))) -> f#(x,f(y,z)) -> f#(x,y) f#(f(f(a(),b()),c()),x) -> f#(b(),f(a(),f(c(),f(b(),x)))) -> f#(x,f(y,z)) -> f#(f(x,y),z) f#(f(f(a(),b()),c()),x) -> f#(b(),x) -> f#(x,f(y,z)) -> f#(x,y) f#(f(f(a(),b()),c()),x) -> f#(b(),x) -> f#(x,f(y,z)) -> f#(f(x,y),z) f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) -> f#(x,f(y,z)) -> f#(x,y) f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) -> f#(x,f(y,z)) -> f#(f(x,y),z) f#(x,f(y,z)) -> f#(f(x,y),z) -> f#(f(f(a(),b()),c()),x) -> f#(b(),x) f#(x,f(y,z)) -> f#(f(x,y),z) -> f#(f(f(a(),b()),c()),x) -> f#(c(),f(b(),x)) f#(x,f(y,z)) -> f#(f(x,y),z) -> f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) f#(x,f(y,z)) -> f#(f(x,y),z) -> f#(f(f(a(),b()),c()),x) -> f#(b(),f(a(),f(c(),f(b(),x)))) f#(x,f(y,z)) -> f#(f(x,y),z) -> f#(x,f(y,z)) -> f#(x,y) f#(x,f(y,z)) -> f#(f(x,y),z) -> f#(x,f(y,z)) -> f#(f(x,y),z) f#(x,f(y,z)) -> f#(x,y) -> f#(f(f(a(),b()),c()),x) -> f#(b(),x) f#(x,f(y,z)) -> f#(x,y) -> f#(f(f(a(),b()),c()),x) -> f#(c(),f(b(),x)) f#(x,f(y,z)) -> f#(x,y) -> f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) f#(x,f(y,z)) -> f#(x,y) -> f#(f(f(a(),b()),c()),x) -> f#(b(),f(a(),f(c(),f(b(),x)))) f#(x,f(y,z)) -> f#(x,y) -> f#(x,f(y,z)) -> f#(x,y) f#(x,f(y,z)) -> f#(x,y) -> f#(x,f(y,z)) -> f#(f(x,y),z) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: f50() -> 2* b0() -> 3* f{#,0}(3,2) -> 1* f0(3,2) -> 3* problem: DPs: f#(f(f(a(),b()),c()),x) -> f#(c(),f(b(),x)) f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) f#(f(f(a(),b()),c()),x) -> f#(b(),f(a(),f(c(),f(b(),x)))) f#(x,f(y,z)) -> f#(x,y) f#(x,f(y,z)) -> f#(f(x,y),z) TRS: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: b0() -> 3* f{#,0}(5,4) -> 1* f{#,0}(31,2) -> 1* f{#,0}(5,3) -> 1* f120() -> 2* c0() -> 5* f0(4,2) -> 4* f0(3,2) -> 4* f0(31,2) -> 31* f0(5,4) -> 31* f0(5,3) -> 31* problem: DPs: f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) f#(f(f(a(),b()),c()),x) -> f#(b(),f(a(),f(c(),f(b(),x)))) f#(x,f(y,z)) -> f#(x,y) f#(x,f(y,z)) -> f#(f(x,y),z) TRS: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) KBO Processor: argument filtering: pi(a) = [] pi(b) = [] pi(f) = 0 pi(c) = [] pi(f#) = 0 usable rules: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) weight function: w0 = 1 w(f#) = w(c) = w(b) = w(a) = 1 w(f) = 0 precedence: a > c > b > f > f# problem: DPs: f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) f#(x,f(y,z)) -> f#(x,y) f#(x,f(y,z)) -> f#(f(x,y),z) TRS: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) Restore Modifier: DPs: f#(f(f(a(),b()),c()),x) -> f#(a(),f(c(),f(b(),x))) f#(x,f(y,z)) -> f#(x,y) f#(x,f(y,z)) -> f#(f(x,y),z) TRS: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: b0() -> 3* f{#,0}(7,6) -> 1* f{#,0}(20,4) -> 1* f{#,0}(7,21) -> 1* f{#,0}(25,2) -> 1* f{#,0}(7,5) -> 1* f{#,0}(20,3) -> 1* c0() -> 5* a0() -> 7* f0(7,5) -> 20* f0(20,3) -> 25* f0(25,2) -> 25* f0(20,4) -> 25* f0(7,6) -> 25* f0(6,2) -> 6* f0(4,2) -> 4* f0(21,2) -> 6* f0(7,21) -> 25* f0(3,2) -> 4* f0(5,4) -> 6* f0(5,3) -> 21* f160() -> 2* problem: DPs: f#(x,f(y,z)) -> f#(x,y) f#(x,f(y,z)) -> f#(f(x,y),z) TRS: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) Size-Change Termination Processor: DPs: TRS: f(f(f(a(),b()),c()),x) -> f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) -> f(f(x,y),z) The DP: f#(x,f(y,z)) -> f#(x,y) has the edges: 0 >= 0 1 > 1 The DP: f#(x,f(y,z)) -> f#(f(x,y),z) has the edges: 1 > 1 Qed