Alternation

We define alternating Turing Machines which are like nondeterministic Turing Machines, except that existential and universal quantifiers alternate. Alternation links up time and space complexities rather well, in that alternating polynomial time equals deterministic polynomial space, and alternating linear space equals deterministic exponential time. Such considerations lead to a two-person game complete in polynomial time, and other games complete in exponential time. We also find that computability on a parallel processing machine is a rather rugged notion, and present two parallel processing models that are polynomially equivalent in their running times. We also show that while n-state alternating finite automata accept only regular sets that can be accepted by 22n-O(logn) state deterministic automata, alternating pushdown automata accept all languages accepted by Turing machines in deterministic exponential time.

Authors

• Ashok K. Chandra
• Larry J. Stockmeyer

Keywords

• Polynomials
• Turing machines
• Automata
• Parallel processing
• Concurrent computing
• Character recognition
• Bridges
• Game theory
• Counting circuits
• Mice
• Time And Space
• Running Time
• Time Complexity
• Space Complexity
• Consequence Of Theorem
• Parallel Machines
• Turing Machine
• Deterministic Time
• Parallel Process Model
• Parallelization
• Language Teaching
• Tree Nodes
• State Machine
• Starting State
• Assignment Of Values
• Input Length
• End Of The Game
• Single Processor
• Number Of Processors
• Time Machine