The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] (simple) multihead finite automata(1hit)

1-1hit
  • Self-Verifying Nondeterministic and Las Vegas Multihead Finite Automata

    Katsushi INOUE  Yasunori TANAKA  Akira ITO  Yue WANG  

     
    PAPER

      Vol:
    E84-A No:5
      Page(s):
    1094-1101

    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.