Abstract
Alternation is a generalization of nondeterminism in which existential and universal quantitiers can alternate during the course of a computation, whereas in a nondeterministic computation there are only existential quantifiers. Alternating Turing machines are defined and shown to accept precisely the recursively enumerable sets. Complexity classes of languages accepted by time- (space-) bounded alternating Turing machines are characterized in terms of complexity classes of languages accepted by space- (time-) bounded deterministic Turing machines. In particular, alternating polynomial time is equivalent to deterministic polynomial space and alternating polynomial space is equivalent to deterministic ‘exponential time. Subrecursive quantifier hierarchies are defined in terms of time- or space-bounded alternating Tufing machines by bounding the number of alternations allowed during computations. Alternating finite-state automata are defined and shown to accept only regular languages, although, in general, 2 2 states are necessary and sufficient to simulate a k-state alternating finite automaton deterministically. Finally, it is shown that alternating pushdown automata are strictly more powerful than nondeterministic pushdown automata. © 1981, ACM. All rights reserved.