What language $L \in NCM$ has $\overline{L} \not \in NCM$?

$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not closed under complement.

However, I've never seen a proof of this given explicitly. In Ibarra's paper, the non-closure is implied because if NCM were closed under complement, subset would be decidable.

However, I've never actually seen an example of a language where $L$ is in $NCM$ but $\overline{L}$ isn't.

I'm wondering, can anyone provide such an example, and preferable, a source describing it that I could cite in a paper?

Letting $L$ be the complement of the language of copies $\{ww \mid w \in \{a, b\}^*\}$, you get your statement. First, it is indeed recognized by a NCM — as is the complement of the language of palindromes. The NCM simply ensures that two positions in the input word chosen non deterministically hold different letters, and checks that they are separated by exactly half the length of the input.
Relying on a combinatorial argument, they show that the complement of $L$ is not recognizable by a Parikh automaton, Lemma 26. Further lemmata have been developed to show that some languages are outside this class (we present a few in this journal paper).
• Where's the reference for the equivalence? I'm wondering if we're talking about different things, since $NCM$ can't accept the language of Palindromes or its complement. – jmite Jul 31 '14 at 4:26