The search functionality is under construction.

IEICE TRANSACTIONS on Information

Path-Bounded One-Way Multihead Finite Automata

Satoshi INOUE, Katsushi INOUE, Akira ITO, Yue WANG

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Information Vol.E88-D No.1 pp.96-99
Publication Date
2005/01/01
Publicized
Online ISSN
DOI
10.1093/ietisy/e88-d.1.96
Type of Manuscript
Special Section LETTER (Special Section on Foundations of Computer Science)
Category

Authors

Keyword