# Is there a strictly non-deterministic one-counter language whose complement is one-counter?

Let $A= \{L \mid L \;\text{is one-counter and $$\bar{L}$$ is also one-counter} \}$

Clearly, $\text{Deterministic one-counter} \subseteq A$

Is it the case that $A = \text{Deterministic one-counter}$?

I know that for context-free languages the analogue is not the case. For example, let $P =\{ ww^r\}$. Then both $P$ and $\bar{P}$ are context-free but $P$ is not deterministic. Hence $A$ defines a (strict) subset of the context-free languages.

The question is: can we construct a similar one-counter example for which the same holds?

• what is "one-counter"? – Ran G. Mar 19 '13 at 16:24
• A PDA with only one kind of symbols (aside from the bottom symbol) on its stack. – frafl Mar 19 '13 at 16:27
• what do you mean by $x_{\lfloor|c|/2\rfloor}=a$ ? – e_noether Mar 20 '13 at 4:20
• @emmy: How would a (nondeterministic) 1CM decide $\overline{L}$? – Shaull Mar 20 '13 at 8:08
• @emmy: Ooops, typo: I meant of course $x_{\lfloor x/2\rfloor}$ i.e. the symbol at the $\lfloor x/2\rfloor$-th position. – frafl Mar 20 '13 at 13:07

In response to Shaull's comment above :

The first one is an image of 1-counter accepting $a^ib^j$ s.t. $j<i$

The secong one is an image of 1-counter accepting $a^ib^j$ s.t. $j>i,\ j<2i$

The third one is an image of 1-counter accepting $a^ib^j$ s.t. $j>2i$

Here a/-/plus means on seeing a, irrespective of the counter value, increment the counter. b/>1?/sub means on seeing b, if counter value is greater than 1, then decrement the counter.

nop => no operation

$\lambda$ => empty string

• Quite a long answer which is essentially just "Because its the union of three languages, each recognizing one interval of $i$s relative to $j$". – frafl Mar 20 '13 at 13:18
• yeah :) just wanted to prove it can be done by 1-counter automata – e_noether Mar 20 '13 at 13:20
• It's OK to elaborate a bit especially if it's a nice exercise for you, but please add a short summary. Additionally you should not use an answer to reply to a comment, but in this case this reply may become an actual answer to your question, so I think it's OK, too. – frafl Mar 20 '13 at 13:26
• Unfortunately, there is no proof here. – Raphael Mar 20 '13 at 13:40