Alternating Multihead Finite Automata with Constant Leaf-Sizes

Hiroshi MATSUNO  Katsushi INOUE  Itsuo TAKANAMI  Hiroshi TANIGUCHI  

IEICE TRANSACTIONS (1976-1990)   Vol.E71   No.10   pp.1006-1012
Publication Date: 1988/10/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automaton, Language and Theory of Computing

Full Text: PDF>>
Buy this Article

We introduce alternating multihead finite automata with constant leaf-sizes (AMHFACLs), and investigate several properties of these automata. The main results of this paper are as follows: (1) two-way sensing AMHFACLs can be simulated by two-way nondeterministic simple multihead finite automata, (2) for one-way AMHFACLs, k+1 heads are better than k, and (3) for one-way alternating simple multihead finite automata with constant leaf-sizes, sensing versions are more powerful than non-sensing versions.