Closure properties of alternating one-way multihead finite automata with constant leaf-sizes Closure Properties of Alternating One-Way Multihead Finite Automata with Constant Leaf-Sizes

Previous Papers introduced alternating multihead finite automata with constant leaf-sizes (AMHFACLs) and investigated several properties of these automata. Leaf-size, in a sense, reflects the number of processors that run in parallel in scanning a given input word. AMHFACLs are more realistic parallel computation models than ordinary alternating multihead finite automata, because of the restriction that the number of processors running in parallel should be constant. This paper examines the closure properties of the class of sets accepted by one-way AMHFACLs and one-way alternating simple multihead finite automata with constant leaf-sizes in the operations of taking union, intersection, complementation, concatenation, Kleene closure, reversal, andε-free homomorphism.