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) Matrix Interpretation Processor: dimension: 1 interpretation: [f#](x0, x1) = x0 + x1, [c] = 1, [f](x0, x1) = x0 + x1, [b] = 0, [a] = 1 orientation: f#(f(f(a(),b()),c()),x) = x + 2 >= x = f#(b(),x) f#(f(f(a(),b()),c()),x) = x + 2 >= x + 1 = f#(c(),f(b(),x)) f#(f(f(a(),b()),c()),x) = x + 2 >= x + 2 = f#(a(),f(c(),f(b(),x))) f#(f(f(a(),b()),c()),x) = x + 2 >= x + 2 = f#(b(),f(a(),f(c(),f(b(),x)))) f#(x,f(y,z)) = x + y + z >= x + y = f#(x,y) f#(x,f(y,z)) = x + y + z >= x + y + z = f#(f(x,y),z) f(f(f(a(),b()),c()),x) = x + 2 >= x + 2 = f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) = x + y + z >= x + y + z = f(f(x,y),z) 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) Matrix Interpretation Processor: dimension: 1 interpretation: [f#](x0, x1) = x0, [c] = 0, [f](x0, x1) = x0, [b] = 0, [a] = 1 orientation: f#(f(f(a(),b()),c()),x) = 1 >= 1 = f#(a(),f(c(),f(b(),x))) f#(f(f(a(),b()),c()),x) = 1 >= 0 = f#(b(),f(a(),f(c(),f(b(),x)))) f#(x,f(y,z)) = x >= x = f#(x,y) f#(x,f(y,z)) = x >= x = f#(f(x,y),z) f(f(f(a(),b()),c()),x) = 1 >= 0 = f(b(),f(a(),f(c(),f(b(),x)))) f(x,f(y,z)) = x >= x = f(f(x,y),z) 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) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: f50() -> 2* f{#,0}(20,3) -> 1* f{#,0}(7,5) -> 1* f{#,0}(7,21) -> 1* f{#,0}(25,2) -> 1* f{#,0}(20,4) -> 1* f{#,0}(7,6) -> 1* a0() -> 7* f0(4,2) -> 4* f0(20,3) -> 25* f0(5,3) -> 21* f0(21,2) -> 6* f0(6,2) -> 6* f0(7,5) -> 20* f0(7,21) -> 25* f0(3,2) -> 4* f0(25,2) -> 25* f0(20,4) -> 25* f0(5,4) -> 6* f0(7,6) -> 25* c0() -> 5* b0() -> 3* 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) Subterm Criterion Processor: simple projection: pi(f#) = 1 problem: 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) Qed