Deterministic two-way one-head pushdown automata are very powerful (Q800088)

Recently \textit{P. Duris} and \textit{Z. Galil} [Theor. Comput. Sci. 21, 39-53 (1982; Zbl 0486.68084)] showed that a deterministic two-way pushdown automaton is more powerful than a deterministic two-way counter automaton by constructing a witness language. The straightforward generalization of the counter is the pushdown tape. Restricting the input alphabet to only one symbol makes the device even simpler. Can we find a natural language over a one-letter alphabet not acceptable by a two-way pushdown automaton with one head? Apparently there has been done work in this area over some time and there was a rumour that the language \(\{a^{n^ 2}|\quad n\in {\mathbb{N}}\}\) is such a witness language. In this paper it is shown that deterministic two-way one-head automata are very powerful even when restricted to a one-letter alphabet. The author shows that if the ''binary version'' of a language belongs to \({\mathbb{P}}\), the class of languages acceptable by deterministic Turing machines in polynomial time, then its ''unary version'' belongs to 2DPDA(1). Here 2DPDA(k), \(k\in {\mathbb{N}}\), denotes the class of languages acceptable by deterministic two-way k-head pushdown automata. For words \(w\in\{1,2\}^*, w=a_ 1a_ 2...a_ n,\) the bijective encoding \(f(w)=\sum^{n}_{i=1}a_ i2^ i\) is used and for a language \(L\subset\{1,1\}^*, un(L)=\{f(w)| w\in L\}.\) Then \(L\subset\{1,2\}^*\) and \(L\in {\mathbb{P}}\) imply \(un(L)\in 2DPDA(1).\)