Portal de Periódicos da CAPES

One-reversal counter machines and multihead automata: Revisited

2012; Elsevier BV; Volume: 454; Linguagem: Inglês

10.1016/j.tcs.2012.04.002

1879-2294

Ehsan Chiniforooshan, Mark Daley, Óscar H. Ibarra, Lila Kari, Shinnosuke Seki,

Machine Learning and Algorithms

We investigate the power of (1-reversal) counter machines (finite automata with multiple counters, where each counter can "reverse" only once, i.e., once a counter decrements, it can no longer increment) and one-way multihead finite automata (finite automata with multiple one-way input heads) as a language acceptor. They can be non-deterministic as well as augmented with a pushdown stack. First, we prove that adding a pushdown stack properly strengthens the deterministic counter machines. Non-deterministic counter machines with a pushdown stack are then compared with multihead finite automata. The proof of their incomparability involves an interesting technique: an assumption that a language be accepted by a non-deterministic counter machine would bring a contradictory algorithm to decide an undecidable language. Furthermore, we will show that over bounded languages, these two kinds of machines have the same power, and neither non-determinism nor a pushdown stack makes them stronger.