Alternating multihead finite automata (Q1116353): Difference between revisions

[See also the review of the preliminary version of this paper, Lect. Notes Comput. Sci. 115, 506-520 (1981; Zbl 0471.68060).] We define alternating multihead finite automata, a generalization of nondeterministic multihead finite automata based on the alternating Turing machine model introduced by \textit{A. K. Chandra}, \textit{D. C. Kozen} and \textit{L. J. Stockmeyer} J. Assoc. Comput. Mach. 28, 114-133 (1981; Zbl 0473.68043). We study the relationships between the classes of languages accepted by alternating multihead finite automata and the classes accepted by deterministic and nondeterministic multihead finite automata and pushdown automata. We also examine basic questions about alternating multihead finite automata (for example, are \(k+1\) heads better than k ?). 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 to our results about alternating multihead finite automata, we obtain several facts about multihead pushdown automata, indicating that the study of alternating multihead finite automata may lead to useful results about nonalternating automata.