For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Alternating Multihead Finite Automata with Constant Leaf-Sizes
Hiroshi MATSUNO Katsushi INOUE Itsuo TAKANAMI Hiroshi TANIGUCHI
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1988/10/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automaton, Language and Theory of Computing
Full Text: PDF>>
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.