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 interpretation: [i#](x0) = 4x0 + 3, [.#](x0, x1) = x0 + 6, [i](x0) = 3x0 + 4, [.](x0, x1) = x0 + x1 + 2, [1] = 6 orientation: .#(.(x,y),z) = x + y + 8 >= y + 6 = .#(y,z) .#(.(x,y),z) = x + y + 8 >= x + 6 = .#(x,.(y,z)) i#(.(x,y)) = 4x + 4y + 11 >= 4x + 3 = i#(x) i#(.(x,y)) = 4x + 4y + 11 >= 4y + 3 = i#(y) i#(.(x,y)) = 4x + 4y + 11 >= 3y + 10 = .#(i(y),i(x)) .(1(),x) = x + 8 >= x = x .(x,1()) = x + 8 >= x = x .(i(x),x) = 4x + 6 >= 6 = 1() .(x,i(x)) = 4x + 6 >= 6 = 1() i(1()) = 22 >= 6 = 1() i(i(x)) = 9x + 16 >= x = x .(i(y),.(y,z)) = 4y + z + 8 >= z = z .(y,.(i(y),z)) = 4y + z + 8 >= z = z .(.(x,y),z) = x + y + z + 4 >= x + y + z + 4 = .(x,.(y,z)) i(.(x,y)) = 3x + 3y + 10 >= 3x + 3y + 10 = .(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