(definition)
Definition: A model of computation proposed by A. K. Chandra, L. Stockmeyere, and D. Kozen, which has two kinds of states, AND and OR. The definition of accepting computation is adjusted accordingly.
See also time/space complexity, Turing machine.
Note: First proposed as a model for parallel computation, it has been widely used to prove complexity bounds on problems.
Author: SKS
A. K. Chandra and L. J. Stockmeyer, Alternation, pages 98-108, and D. Kozen, On Parallelism in Turing Machines, pages 89-97, both in Proc. Seventeenth Annual IEEE Symposium on Foundations of Computer Science, 1976.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 December 2005.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Sandeep Kumar Shukla, "alternation", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 14 December 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/alternation.html
