Alternation - Major Results in Automata Theory
Mathematics Accomplishment | 1981
Where the work was done: IBM T.J. Watson Research Center
What we accomplished: Excerpting from the paper's abstract, "Alternation is a generalization of nondeterminism . . . Alternating Turing machines are defined . . . [It is shown that] alternating polynomial time is equivalent to deterministic polynomial space and alternating polynomial space is equivalent to deterministic 'exponential time . . . Finally, it is shown that alternating pushdown automata are strictly more powerful than nondeterministic pushdown automata.