ALTERNATING MULTIHEAD FINITE AUTOMATA

We define alternating multihead finite automata, a generalization of nondeterministic multihead finite automata based on the alternating Turing machine model introduced by A.K. Chandra et al. We study the relationships between the classes of languages accepted by alternating multihead finite automata and pushdown automata. We also examine basic questions about alternating multihead finite automata. We conclude by placing upper bounds on the deterministic time and space complexity of the classes of languages accepted by alternating multihead finite automata. As corollaries, we obtain several facts about multihead pushdown automata.