<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-02-28T14:27:05.633Z
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*!
Abuzer Yakaryilmaz
CC BY-SA 3.0
2014-02-28T10:43:27.777Z
2014-02-28T10:43:27.777Z
dd1
<p>One-way alternating pushdown automata (1APDA) can recognize any language in $ DTIME(2^{O(n)}) $ <a href="http://dl.acm.org/citation.cfm?doid=322234.322243">(Alternation by Chandra, Kozen, and Stockmeyer, 1981)</a>. 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.</p>

<p>Can 1ACAs recognize some <strong>unary non-regular</strong> languages?</p>

<p>Note that one-way nondeterministic pushdown automata can recognize only unary regular languages.</p>

<automata-theory><counter-automata><unary-languages>
Can one-way alternating automata with one-counter recognize some unary non-regular languages?
Abuzer Yakaryilmaz
# Can one-way alternating automata with one-counter recognize some unary non-regular languages?

(Asked by: username_0 on 2013-09-17)

One-way alternating pushdown automata (1APDA) can recognize any language in $ DTIME(2^{O(n)}) $ [(Alternation by Chandra, Kozen, and Stockmeyer, 1981)](http://dl.acm.org/citation.cfm?doid=322234.322243). 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.

**Tags:** automata-theory, counter-automata, unary-languages


---

## 1 answers

### Answer by username_1 on 2014-02-28. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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*!  

---

