 | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (May 2011) |
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer[1] and independently by Kozen[2] in 1976, with a joint journal publication in 1981.[3]
- ^ Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternation". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 98–108. doi:10.1109/SFCS.1976.4.
- ^ Kozen, D. (1976). "On parallelism in Turing machines". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 89–97. doi:10.1109/SFCS.1976.20. hdl:1813/7056.
- ^ Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation" (PDF). Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. S2CID 238863413. Archived from the original (PDF) on April 12, 2016.