One-way simple multihead finite automata

DOI 9 Citations Open Access

Search this article

Description

AbstractThe 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.

Journal

Citations (9)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top