Alternation

Abstract

Alternation is a generalization of nondeterminism in which existential and universal quanti- tiers 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 determin- istic '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 determin- istically. Finally, it is shown that alternating pushdown automata are strictly more powerful than nondeterministic pushdown automata.