11
$\begingroup$

One-way alternating pushdown automata (1APDA) can recognize any language in $ DTIME(2^{O(n)}) $ (Alternation by Chandra, Kozen, and Stockmeyer, 1981). By replacing a pushdown storage of a 1APDA with a counter, we can obtain a one-way alternating automaton with one-counter (1ACA). My question is about 1ACAs on unary languages.

Can 1ACAs recognize some unary non-regular languages?

Note that one-way nondeterministic pushdown automata can recognize only unary regular languages.

$\endgroup$
6
$\begingroup$

Yes. Consider the language $L = \{ a^n \mid n = 2^s, s \geq 0 \}$ and construct a one-way alternating one-counter automaton recognizing $L$ in the following way. First, the automaton starts increasing the value of the counter and guesses when to stop, that is, guesses some value $m$. Then it branches universally: the first branch checks that the length of the input is precisely $2 m$, and the second branch moves $m$ cells forward on the input and checks that the remainder is in $L$, by going to the initial control state. Now add a base case: let the device accept if the input tape is exactly of length $1$, by making a nondeterministic guess at the initial state. That completes the construction.

In a similar fashion, one can get products of the form $n = k_1^{s_1} \ldots k_r^{s_r}$, with $k_1, \ldots, k_r$ fixed and $s_1, \ldots, s_r$ arbitrary.

$\endgroup$
  • 1
    $\begingroup$ Thank you for the answer. I got the same answer from Pavol Duris (via private communication) which will appear in a paper soon. I was planning to post the answer after the paper appears online. (There can be even some stronger results.) Anyway, your answer is certainly accepted answer! $\endgroup$ – Abuzer Yakaryilmaz Feb 28 '14 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.