The search functionality is under construction.

Keyword Search Result

[Keyword] one-way multihead finite automata(1hit)

1-1hit
  • Path-Bounded One-Way Multihead Finite Automata

    Satoshi INOUE  Katsushi INOUE  Akira ITO  Yue WANG  

     
    LETTER

      Vol:
    E88-D No:1
      Page(s):
    96-99

    For each positive integer r 1, a nondeterministic machine M is r path-bounded if for any input word x, there are r computation paths of M on x. This paper investigates the accepting powers of path-bounded one-way (simple) multihead nondeterministic finite automata. It is shown that for each k 2 and r 1, there is a language accepted by an (r + 1) path-bounded one-way nondeterministic k head finite automaton, but not accepted by any r path-bounded one-way nondeterministic k head finite automaton whether or not simple.