Portal de Periódicos da CAPES

On partially blind multihead finite automata

2006; Elsevier BV; Volume: 356; Issue: 1-2 Linguagem: Inglês

10.1016/j.tcs.2006.01.030

1879-2294

Óscar H. Ibarra, Bala Ravikumar,

DNA and Biological Computing

This work is concerned with 1-way multihead finite automata (FA), both deterministic and nondeterministic, in which the symbol under only one head controls its move. We call such a FA a partially blind multihead FA. We show some results regarding the decision problems and closure properties of blind multihead DFA and NFA. We also compare these devices with 1-way NFA augmented by reversal bounded counters. Finally, we also present some results regarding the simulation of a partially blind DFA and NFA by a probabilistic finite automaton.