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

Question

$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?

Answer 1

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.

Now Parikh Automata were introduced by Klaedkte and Rueß in ICALP'03. The technical report version, available on Klaedkte's webpage, states the equivalence of Parikh Automata and NCM as Theorem 29 and 31.

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).