|
|
Please login using the form on menu list.
It is required to login for Full-Text PDF.
|
Path-Bounded One-Way Multihead Finite Automata
Satoshi INOUE
Katsushi INOUE
Akira ITO
Yue WANG
Publication
IEICE TRANSACTIONS on Information and Systems Vol.E88-D No.1 pp.96-99
Publication Date: 2005/01/01
Online ISSN:
Print ISSN: 0916-8532
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science)
Category:
Keyword:
one-way multihead finite automata,
simple one-way multihead finite automata,
path-bounded computation,
degree of nondeterminism,
Full Text: PDF(92.4KB)
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.
|
|
