<p>Letting $L$ be the <em>complement</em> 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.</p>

<p>Now Parikh Automata were introduced by Klaedkte and Rueß in ICALP'03.  The technical report version, available <a href="http://www.inf.ethz.ch/personal/felixkl/papers/tr177-card-new.ps.gz" rel="nofollow">on Klaedkte's webpage</a>, states the equivalence of Parikh Automata and NCM as Theorem 29 and 31.</p>

<p>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 <a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=8735574&amp;fileId=S0988375412000136" rel="nofollow">this journal paper</a>).</p>

CC BY-SA 3.0
2014-07-31T04:26:48.353Z
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.
Joey Eremondi
CC BY-SA 3.0
2014-07-31T08:58:48.143Z
I edited my answer to give more information.  In particular, I had L and the complement of L mixed up.
Michaël Cadilhac
CC BY-SA 3.0
2014-07-30T23:38:38.100Z
2014-07-31T08:57:59.893Z
2014-07-31T08:57:59.893Z
Michaël Cadilhac
<p>$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.</p>

<p>However, I've never seen a proof of this given explicitly. In <a href="http://www.lsv.ens-cachan.fr/~demri/p116-ibarra.pdf">Ibarra's paper</a>,
the non-closure is implied because if NCM were closed under complement, subset would be decidable.</p>

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

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

<reference-request><fl.formal-languages><automata-theory><decidability><undecidability>
What language $L \in NCM$ has $\overline{L} \not \in NCM$?
Joey Eremondi
# What language $L \in NCM$ has $\overline{L} \not \in NCM$?

(Asked by: username_0 on 2014-07-30)

$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](http://www.lsv.ens-cachan.fr/~demri/p116-ibarra.pdf),
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?

**Tags:** reference-request, fl.formal-languages, automata-theory, decidability, undecidability


---

## 1 answers

### Answer by username_1 on 2014-07-30. Score: 5 | Accepted answer

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](http://www.inf.ethz.ch/personal/felixkl/papers/tr177-card-new.ps.gz), 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](http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8735574&fileId=S0988375412000136)).

> **Comments:**
> **username_0**: 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.  
> **username_1**: I edited my answer to give more information.  In particular, I had L and the complement of L mixed up.  

---

