YES Problem: +(+(x,y),z) -> +(x,+(y,z)) +(f(x),f(y)) -> f(+(x,y)) +(f(x),+(f(y),z)) -> +(f(+(x,y)),z) Proof: DP Processor: DPs: +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) +#(f(x),f(y)) -> +#(x,y) +#(f(x),+(f(y),z)) -> +#(x,y) +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) TRS: +(+(x,y),z) -> +(x,+(y,z)) +(f(x),f(y)) -> f(+(x,y)) +(f(x),+(f(y),z)) -> +(f(+(x,y)),z) EDG Processor: DPs: +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) +#(f(x),f(y)) -> +#(x,y) +#(f(x),+(f(y),z)) -> +#(x,y) +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) TRS: +(+(x,y),z) -> +(x,+(y,z)) +(f(x),f(y)) -> f(+(x,y)) +(f(x),+(f(y),z)) -> +(f(+(x,y)),z) graph: +#(f(x),f(y)) -> +#(x,y) -> +#(+(x,y),z) -> +#(y,z) +#(f(x),f(y)) -> +#(x,y) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(f(x),f(y)) -> +#(x,y) -> +#(f(x),f(y)) -> +#(x,y) +#(f(x),f(y)) -> +#(x,y) -> +#(f(x),+(f(y),z)) -> +#(x,y) +#(f(x),f(y)) -> +#(x,y) -> +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) -> +#(f(x),f(y)) -> +#(x,y) +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) -> +#(f(x),+(f(y),z)) -> +#(x,y) +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) -> +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) +#(f(x),+(f(y),z)) -> +#(x,y) -> +#(+(x,y),z) -> +#(y,z) +#(f(x),+(f(y),z)) -> +#(x,y) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(f(x),+(f(y),z)) -> +#(x,y) -> +#(f(x),f(y)) -> +#(x,y) +#(f(x),+(f(y),z)) -> +#(x,y) -> +#(f(x),+(f(y),z)) -> +#(x,y) +#(f(x),+(f(y),z)) -> +#(x,y) -> +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) +#(+(x,y),z) -> +#(y,z) -> +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(y,z) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) -> +#(f(x),f(y)) -> +#(x,y) +#(+(x,y),z) -> +#(y,z) -> +#(f(x),+(f(y),z)) -> +#(x,y) +#(+(x,y),z) -> +#(y,z) -> +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(f(x),f(y)) -> +#(x,y) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(f(x),+(f(y),z)) -> +#(x,y) +#(+(x,y),z) -> +#(x,+(y,z)) -> +#(f(x),+(f(y),z)) -> +#(f(+(x,y)),z) Matrix Interpretation Processor: dimension: 1 interpretation: [+#](x0, x1) = x0 + x1, [f](x0) = x0 + 1, [+](x0, x1) = x0 + x1 orientation: +#(+(x,y),z) = x + y + z >= y + z = +#(y,z) +#(+(x,y),z) = x + y + z >= x + y + z = +#(x,+(y,z)) +#(f(x),f(y)) = x + y + 2 >= x + y = +#(x,y) +#(f(x),+(f(y),z)) = x + y + z + 2 >= x + y = +#(x,y) +#(f(x),+(f(y),z)) = x + y + z + 2 >= x + y + z + 1 = +#(f(+(x,y)),z) +(+(x,y),z) = x + y + z >= x + y + z = +(x,+(y,z)) +(f(x),f(y)) = x + y + 2 >= x + y + 1 = f(+(x,y)) +(f(x),+(f(y),z)) = x + y + z + 2 >= x + y + z + 1 = +(f(+(x,y)),z) problem: DPs: +#(+(x,y),z) -> +#(y,z) +#(+(x,y),z) -> +#(x,+(y,z)) TRS: +(+(x,y),z) -> +(x,+(y,z)) +(f(x),f(y)) -> f(+(x,y)) +(f(x),+(f(y),z)) -> +(f(+(x,y)),z) Subterm Criterion Processor: simple projection: pi(+#) = 0 problem: DPs: TRS: +(+(x,y),z) -> +(x,+(y,z)) +(f(x),f(y)) -> f(+(x,y)) +(f(x),+(f(y),z)) -> +(f(+(x,y)),z) Qed