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.5KB)
>>Buy this Article


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.