Unary languages recognized by two-way deterministic counter automata

Question

2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language: \begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation}

Is there any other nontrivial unary language recognized by 2dca's?

Remark that it is still unknown whether 2dca's can recognize $ \mathtt{SQUARE} = \lbrace 0^{n^2} \mid n \geq 0 \rbrace $?

---

DEFINITION: A 2dca is a two-way deterministic finite automaton with a counter. A 2dca can test whether the value of the counter is zero or not, and increment or decrement the value of the counter by 1 in each step.

Answer 1

This is only an idea that came to my mind while reading Marvin L. Minsky, "Recursive Unsolvability of Post's Problem of Tag and other Topics in Theory of Turing Machines"; in particular the famous theorem Ia:

Theorem Ia: We can represent any partial recursive function $f(n)$ by a program operating on two integers $S_1$ and $S_2$ using instructions $I_j$ of the forms:
(i) ADD 1 to $S_j$, and go to $I_{j_1}$
(ii) SUBTRACT 1 from $S_j$, if $S_j \neq 0$ and go to $I_{j_1}$, otherwise go to $I_{j_2}$
That is, we can construct such a program that starts with $S_1 = 2^n$ and $S_2 = 0$ and eventually stops with $S_1 = 2^{f(n)}$ and $S_2 = 0$

If you have a two way DFA with one counter over a (semi)infinite tape where the input is given in unary: $\$1^{2^n}000...$ then the DFA can:

1. read the unary input (and store it in the counter);
2. work on the $0^\infty$ part of the tape and use the distance from the $1$s as the second counter.

so it can simulate a Turing complete two counters machine.

Now, if you have a recursive function $f(n)$ that runs in time $T(n)$ on a standard Turing machine, a two way DFA with one counter that starts on the finite tape $\$1^m\$ \;$ (where $m = 2^n3^{T'(n)}$ and $T'(n) \gg T(n)$) can:

1. read the unary input (and store it in the counter);
2. return to leftmost symbol;
3. divide the counter by 3 until the counter contains $2^n$ in this way: go right looping from states $q_{z_0}, q_{z_1}, q_{z_2}$ and subtracting 1; if counter reaches 0 in state $q_{z_0}$ go to leftmost symbol adding +1 and continue the division loop, otherwise add 1 (if in state $q_{z_1}$) or 2 (if in state $q_{z_2}$) and go to leftmost symbol adding +3 (i.e. recover the previous value of the counter not divisible by 3) and proceed with step 4.;
4. at this point the counter contains $2^n$;
5. calculate $2^{f(n)}$ using the $T'(n)$ space available on the right as the second counter (the value of the second counter is the distance from the leftmost symbol $\$$).

So with the special input encoding described above that gives it enough space on the finite tape, a two-way DFA with one counter and unary alphabet can compute every recursive function.

If the approach is correct, it would be interesting to reason about how to choose $T'(n) \gg T(n)$ or when it is enough to pick a large odd $k \gg 2$ and encode the input as $1^m$, $m = 2^n k^n$

Answer 2

By non-trivial, I assume you mean a language L that can't be accepted by a 1dca. Here seems to be such a language:

CENTER = { w | w is over {0,1}* and w = x1y for some x, y such that |x| = |y|}

This language can't be accepted by 1dca, but CAN be accepted by 1nca. It can be accepted by a 2dca. Details are left as exercise.