Remarks on two-way automata with weak-counters (Q793509)

A counter which stores any nonnegative integer has three kinds of operations: add, subtract and zero test. The weak-counter is defined as a counter that cannot be tested for zero. Machines with multiple weak- counters have received considerable attention from several points. This paper gives some observations on two-way automata with weak-counters. Two-way finite, pushdown and stack automata are well-known examples of two-way automata. First the author investigates how additional weak- counters affect the recognition power of these automata. It is proved that such deterministic automata augmented with one weak-counter have the same recognition ability as those with k weak-counters for all \(k\geq 1\). Second he shows that any two-way nondeterministic one-weak-counter machine can be simulated by a two-way three-counter machine which accepts in linear time. As a corollary of this fact, it is proved that the language \(\{ww^ R| w\quad is\quad in\quad \{0,1\}^*\}\) cannot be recognized by any two-way nondeterministic one-weak-counter machine although this language is recognizable by a two-way deterministic one- counter machine.