Alternation - Major Results in Automata Theory
Mathematics Accomplishment | 1981
IBM researchers: Ashok K. Chandra, Dexter C. Kozen, Larry J. Stockmeyer
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.
Related links: Alternation (Journal of the ACM, Volume 28 Issue 1, January 1981); Wikipedia entry on Alternating Turing Machine.
BACK TO IBM RESEARCH ACCOMPLISHMENTS