Alternation
- 1 October 1976
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 98-108
- https://doi.org/10.1109/sfcs.1976.4
Abstract
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.Keywords
This publication has 19 references indexed in Scilit:
- On parallelism in turing machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- A characterization of the power of vector machinesJournal of Computer and System Sciences, 1976
- Translational lemmas, polynomial time, and (log n)j-spaceTheoretical Computer Science, 1976
- On Dedekind's Problem: The Number of Isotone Boolean Functions. IITransactions of the American Mathematical Society, 1975
- On the power of multiplication in random access machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- Complete problems for deterministic polynomial timePublished by Association for Computing Machinery (ACM) ,1974
- Economy of description by automata, grammars, and formal systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1971
- Time- and tape-bounded turing acceptors and AFLsJournal of Computer and System Sciences, 1970
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- Hierarchies of memory limited computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965