# 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"? Mar 19, 2013 at 16:24
• A PDA with only one kind of symbols (aside from the bottom symbol) on its stack. Mar 19, 2013 at 16:27
• what do you mean by $x_{\lfloor|c|/2\rfloor}=a$ ? Mar 20, 2013 at 4:20
• @emmy: How would a (nondeterministic) 1CM decide $\overline{L}$? Mar 20, 2013 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. Mar 20, 2013 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$". Mar 20, 2013 at 13:18
• yeah :) just wanted to prove it can be done by 1-counter automata Mar 20, 2013 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. Mar 20, 2013 at 13:26
• Unfortunately, there is no proof here. Mar 20, 2013 at 13:40