Self-Verifying Nondeterministic and Las Vegas Multihead Finite Automata

Katsushi INOUE, Yasunori TANAKA, Akira ITO, Yue WANG

Summary :

This paper is concerned with a comparative study of the accepting powers of deterministic, Las Vegas, self-verifying nondeterminisic, and nondeterministic (simple) multihead finite automata. We show that (1) for each k 2, one-way deterministic k-head (resp., simple k-head) finite automata are less powerful than one-way Las Vegas k-head (resp., simple k-head) finite automata, (2) there is a language accepted by a one-way self-verifying nondeterministic simple 2-head finite automaton, but not accepted by any one-way deterministic simple multihead finite automaton, (3) there is a language accepted by a one-way nondeterministic 2-head (resp., simple 2-head) finite automaton, but not accepted by any one-way self-verifying nondeterministic multihead (resp., simple multihead) finite automaton, (4) for each k 1, two-way Las Vegas k-head (resp., simple k-head) finite automata have the same accepting powers as two-way self-verifying nondeterministic k-head (resp., simple k-head) finite automata, and (5) two-way Las Vegas simple 2-head finite automata are more powerful than two-way deterministic simple 2-head finite automata.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1094-1101
• Publication Date: 2001/05/01
• Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Authors

Katsushi INOUE
Yasunori TANAKA
Akira ITO
Yue WANG

Keyword

determinism,  self-verifying nondeterminism,  Las Vegas,  (simple) multihead finite automata