Alternating simple multihead finite automata (Q1058853)

This paper introduces the alternating simple multihead finite automaton (ASPMHFA), which can be considered as an alternating version of a simple multihead finite automaton (SPMHFA). We first show that ASPMHFA's are equivalent to ordinary alternating multihead finite automata. We investigate a relationship among the accepting powers of SPMHFA's, ASPMHFA's, and ASPMHFA's with only universal states. We next introduce a simple, natural complexity measure for ASPMHFA's, called 'leaf-size', and provide a spectrum of complexity classes of ASPMHFA's, based on simultaneously leaf-size, the number of heads, and the move directions of heads. We finally investigate closure properties (under Boolean operations) of ASPMHFA's.