17
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Could you add a link to a definition of a 2DCA ? $\endgroup$ – Suresh Venkat Jul 8 '12 at 20:50
  • 3
    $\begingroup$ @SureshVenkat: I added a reference and also a definition. $\endgroup$ – Abuzer Yakaryilmaz Jul 8 '12 at 22:00
  • 1
    $\begingroup$ @AbuzerYakaryilmaz: for every fixed $k$ it can recognize $\{0^{k^n} : n \geq 0\}$ $\endgroup$ – Marzio De Biasi May 7 '13 at 17:19
  • $\begingroup$ @MarzioDeBiasi: The algorithm for $ \mathtt{POWER} $ can be easily generalized to $ \mathtt{POWER_k} = \{0^{k^n} \mid n \geq 0\} $, where $ k \geq 3 $. Therefore, these languages are quite trivial for me. $\endgroup$ – Abuzer Yakaryilmaz May 8 '13 at 5:16
  • 1
    $\begingroup$ Hm, in fact I think this way I just end up at the same observation what Marzio made already, so nothing new in what I said. I am still interested though in whether we need to read the endmarker more than a bounded number of times. $\endgroup$ – domotorp Jul 16 '13 at 13:56
6
$\begingroup$

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$

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The OP asks for unary languages (the input is given as $\$1^n\$$) $\endgroup$ – Marzio De Biasi May 31 '13 at 19:24

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.