YES Problem: f(a(),f(b(),x)) -> f(b(),f(a(),x)) f(b(),f(c(),x)) -> f(c(),f(b(),x)) f(c(),f(a(),x)) -> f(a(),f(c(),x)) Proof: DP Processor: DPs: f#(a(),f(b(),x)) -> f#(a(),x) f#(a(),f(b(),x)) -> f#(b(),f(a(),x)) f#(b(),f(c(),x)) -> f#(b(),x) f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) f#(c(),f(a(),x)) -> f#(c(),x) f#(c(),f(a(),x)) -> f#(a(),f(c(),x)) TRS: f(a(),f(b(),x)) -> f(b(),f(a(),x)) f(b(),f(c(),x)) -> f(c(),f(b(),x)) f(c(),f(a(),x)) -> f(a(),f(c(),x)) EDG Processor: DPs: f#(a(),f(b(),x)) -> f#(a(),x) f#(a(),f(b(),x)) -> f#(b(),f(a(),x)) f#(b(),f(c(),x)) -> f#(b(),x) f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) f#(c(),f(a(),x)) -> f#(c(),x) f#(c(),f(a(),x)) -> f#(a(),f(c(),x)) TRS: f(a(),f(b(),x)) -> f(b(),f(a(),x)) f(b(),f(c(),x)) -> f(c(),f(b(),x)) f(c(),f(a(),x)) -> f(a(),f(c(),x)) graph: f#(c(),f(a(),x)) -> f#(c(),x) -> f#(c(),f(a(),x)) -> f#(c(),x) f#(c(),f(a(),x)) -> f#(c(),x) -> f#(c(),f(a(),x)) -> f#(a(),f(c(),x)) f#(c(),f(a(),x)) -> f#(a(),f(c(),x)) -> f#(a(),f(b(),x)) -> f#(a(),x) f#(c(),f(a(),x)) -> f#(a(),f(c(),x)) -> f#(a(),f(b(),x)) -> f#(b(),f(a(),x)) f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) -> f#(c(),f(a(),x)) -> f#(c(),x) f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) -> f#(c(),f(a(),x)) -> f#(a(),f(c(),x)) f#(b(),f(c(),x)) -> f#(b(),x) -> f#(b(),f(c(),x)) -> f#(b(),x) f#(b(),f(c(),x)) -> f#(b(),x) -> f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) f#(a(),f(b(),x)) -> f#(b(),f(a(),x)) -> f#(b(),f(c(),x)) -> f#(b(),x) f#(a(),f(b(),x)) -> f#(b(),f(a(),x)) -> f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) f#(a(),f(b(),x)) -> f#(a(),x) -> f#(a(),f(b(),x)) -> f#(a(),x) f#(a(),f(b(),x)) -> f#(a(),x) -> f#(a(),f(b(),x)) -> f#(b(),f(a(),x)) Matrix Interpretation Processor: dimension: 1 interpretation: [f#](x0, x1) = x0 + x1, [c] = 0, [f](x0, x1) = x0 + x1 + 1, [b] = 0, [a] = 1 orientation: f#(a(),f(b(),x)) = x + 2 >= x + 1 = f#(a(),x) f#(a(),f(b(),x)) = x + 2 >= x + 2 = f#(b(),f(a(),x)) f#(b(),f(c(),x)) = x + 1 >= x = f#(b(),x) f#(b(),f(c(),x)) = x + 1 >= x + 1 = f#(c(),f(b(),x)) f#(c(),f(a(),x)) = x + 2 >= x = f#(c(),x) f#(c(),f(a(),x)) = x + 2 >= x + 2 = f#(a(),f(c(),x)) f(a(),f(b(),x)) = x + 3 >= x + 3 = f(b(),f(a(),x)) f(b(),f(c(),x)) = x + 2 >= x + 2 = f(c(),f(b(),x)) f(c(),f(a(),x)) = x + 3 >= x + 3 = f(a(),f(c(),x)) problem: DPs: f#(a(),f(b(),x)) -> f#(b(),f(a(),x)) f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) f#(c(),f(a(),x)) -> f#(a(),f(c(),x)) TRS: f(a(),f(b(),x)) -> f(b(),f(a(),x)) f(b(),f(c(),x)) -> f(c(),f(b(),x)) f(c(),f(a(),x)) -> f(a(),f(c(),x)) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: a0() -> 3* f50() -> 2* f{#,0}(5,4) -> 1* b0() -> 5* f0(3,2) -> 4* f0(5,4) -> 4* problem: DPs: f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) f#(c(),f(a(),x)) -> f#(a(),f(c(),x)) TRS: f(a(),f(b(),x)) -> f(b(),f(a(),x)) f(b(),f(c(),x)) -> f(c(),f(b(),x)) f(c(),f(a(),x)) -> f(a(),f(c(),x)) Matrix Interpretation Processor: dimension: 1 interpretation: [f#](x0, x1) = x1, [c] = 0, [f](x0, x1) = x0 + x1, [b] = 0, [a] = 1 orientation: f#(b(),f(c(),x)) = x >= x = f#(c(),f(b(),x)) f#(c(),f(a(),x)) = x + 1 >= x = f#(a(),f(c(),x)) f(a(),f(b(),x)) = x + 1 >= x + 1 = f(b(),f(a(),x)) f(b(),f(c(),x)) = x >= x = f(c(),f(b(),x)) f(c(),f(a(),x)) = x + 1 >= x + 1 = f(a(),f(c(),x)) problem: DPs: f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) TRS: f(a(),f(b(),x)) -> f(b(),f(a(),x)) f(b(),f(c(),x)) -> f(c(),f(b(),x)) f(c(),f(a(),x)) -> f(a(),f(c(),x)) Matrix Interpretation Processor: dimension: 1 interpretation: [f#](x0, x1) = x1, [c] = 1, [f](x0, x1) = x0 + x1, [b] = 0, [a] = 1 orientation: f#(b(),f(c(),x)) = x + 1 >= x = f#(c(),f(b(),x)) f(a(),f(b(),x)) = x + 1 >= x + 1 = f(b(),f(a(),x)) f(b(),f(c(),x)) = x + 1 >= x + 1 = f(c(),f(b(),x)) f(c(),f(a(),x)) = x + 2 >= x + 2 = f(a(),f(c(),x)) problem: DPs: TRS: f(a(),f(b(),x)) -> f(b(),f(a(),x)) f(b(),f(c(),x)) -> f(c(),f(b(),x)) f(c(),f(a(),x)) -> f(a(),f(c(),x)) Qed