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)) CDG 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#(a(),f(c(),x)) f#(c(),f(a(),x)) -> f#(c(),x) -> f#(c(),f(a(),x)) -> f#(c(),x) f#(b(),f(c(),x)) -> f#(b(),x) -> f#(b(),f(c(),x)) -> f#(c(),f(b(),x)) f#(b(),f(c(),x)) -> f#(b(),x) -> f#(b(),f(c(),x)) -> f#(b(),x) f#(a(),f(b(),x)) -> f#(a(),x) -> f#(a(),f(b(),x)) -> f#(b(),f(a(),x)) f#(a(),f(b(),x)) -> f#(a(),x) -> f#(a(),f(b(),x)) -> f#(a(),x) Restore Modifier: 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)) SCC Processor: #sccs: 3 #rules: 3 #arcs: 6/36 DPs: f#(a(),f(b(),x)) -> f#(a(),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] = 1, [a] = 0 orientation: f#(a(),f(b(),x)) = x + 1 >= x = f#(a(),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 >= x = 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 DPs: f#(b(),f(c(),x)) -> 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] = 0 orientation: f#(b(),f(c(),x)) = x + 1 >= x = f#(b(),x) f(a(),f(b(),x)) = x >= x = 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 + 1 >= x + 1 = 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 DPs: f#(c(),f(a(),x)) -> 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#(c(),f(a(),x)) = x + 1 >= x = 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: 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