One-way simple multihead finite automata
1979; Elsevier BV; Volume: 9; Issue: 3 Linguagem: Inglês
10.1016/0304-3975(79)90033-1
ISSN1879-2294
AutoresKatsushi Inoue, Itsuo Takanami, Akira Nakamura, Tadashi Ae,
Tópico(s)DNA and Biological Computing
ResumoThe first half of this paper investigates the accepting powers of various types of simple one-way multihead finite automata. It is shown that (1)for each k ⩾1, simple one-way ( k +1)-head finite automata are more powerful than simple one-way k -head finite automata. (2)for each k ⩾2, nondeterministic simple one-way k -head finite automata are more powerful than deterministic ones, and (3)for each k ⩾2, sensing simple one-way k -head finite automata are more powerful than non-sensing ones. In the latter half, closure properties for various types of simple one-way multihead finite automata are investigated. Finally, we demonstrate that languages accepted by nondeterministic sensing simple one-way 2-head finite automata are related to some open problem concerning deterministic and nondeterministic tape-bounded Turing computations.
Referência(s)