YES Problem: .(1(),x) -> x .(x,1()) -> x .(i(x),x) -> 1() .(x,i(x)) -> 1() i(1()) -> 1() i(i(x)) -> x .(i(y),.(y,z)) -> z .(y,.(i(y),z)) -> z .(.(x,y),z) -> .(x,.(y,z)) i(.(x,y)) -> .(i(y),i(x)) Proof: DP Processor: DPs: .#(.(x,y),z) -> .#(y,z) .#(.(x,y),z) -> .#(x,.(y,z)) i#(.(x,y)) -> i#(x) i#(.(x,y)) -> i#(y) i#(.(x,y)) -> .#(i(y),i(x)) TRS: .(1(),x) -> x .(x,1()) -> x .(i(x),x) -> 1() .(x,i(x)) -> 1() i(1()) -> 1() i(i(x)) -> x .(i(y),.(y,z)) -> z .(y,.(i(y),z)) -> z .(.(x,y),z) -> .(x,.(y,z)) i(.(x,y)) -> .(i(y),i(x)) Matrix Interpretation Processor: dim=1 usable rules: .(1(),x) -> x .(x,1()) -> x .(i(x),x) -> 1() .(x,i(x)) -> 1() i(1()) -> 1() i(i(x)) -> x .(i(y),.(y,z)) -> z .(y,.(i(y),z)) -> z .(.(x,y),z) -> .(x,.(y,z)) i(.(x,y)) -> .(i(y),i(x)) interpretation: [i#](x0) = 4x0, [.#](x0, x1) = x0, [i](x0) = 4x0 + 5, [.](x0, x1) = x0 + x1 + 3, [1] = 6 orientation: .#(.(x,y),z) = x + y + 3 >= y = .#(y,z) .#(.(x,y),z) = x + y + 3 >= x = .#(x,.(y,z)) i#(.(x,y)) = 4x + 4y + 12 >= 4x = i#(x) i#(.(x,y)) = 4x + 4y + 12 >= 4y = i#(y) i#(.(x,y)) = 4x + 4y + 12 >= 4y + 5 = .#(i(y),i(x)) .(1(),x) = x + 9 >= x = x .(x,1()) = x + 9 >= x = x .(i(x),x) = 5x + 8 >= 6 = 1() .(x,i(x)) = 5x + 8 >= 6 = 1() i(1()) = 29 >= 6 = 1() i(i(x)) = 16x + 25 >= x = x .(i(y),.(y,z)) = 5y + z + 11 >= z = z .(y,.(i(y),z)) = 5y + z + 11 >= z = z .(.(x,y),z) = x + y + z + 6 >= x + y + z + 6 = .(x,.(y,z)) i(.(x,y)) = 4x + 4y + 17 >= 4x + 4y + 13 = .(i(y),i(x)) problem: DPs: TRS: .(1(),x) -> x .(x,1()) -> x .(i(x),x) -> 1() .(x,i(x)) -> 1() i(1()) -> 1() i(i(x)) -> x .(i(y),.(y,z)) -> z .(y,.(i(y),z)) -> z .(.(x,y),z) -> .(x,.(y,z)) i(.(x,y)) -> .(i(y),i(x)) Qed