Name
Abstract | ||
|---|---|---|
Alternation is a generalization of nondeterminism in which existential and universal quanti- tiers can alternate during the course of a computation, whereas in a nondeterministic computation there are only existential quantifiers. Alternating Turing machines are defined and shown to accept precisely the recursively enumerable sets. Complexity classes of languages accepted by time- (space-) bounded alternating Turing machines are characterized in terms of complexity classes of languages accepted by space- (time-) bounded deterministic Turing machines. In particular, alternating polynomial time is equivalent to deterministic polynomial space and alternating polynomial space is equivalent to determin- istic 'exponential time. Subrecursive quantifier hierarchies are defined in terms of time- or space-bounded alternating Tufing machines by bounding the number of alternations allowed during computations. Alternating finite-state automata are defined and shown to accept only regular languages, although, in general, 2 2 states are necessary and sufficient to simulate a k-state alternating finite automaton determin- istically. Finally, it is shown that alternating pushdown automata are strictly more powerful than nondeterministic pushdown automata. |
Year | DOI | Venue |
|---|---|---|
1981 | 10.1145/322234.322243 | J. ACM |
Keywords | DocType | Volume |
complexity,alternation | Journal | 28 |
Issue | Citations | PageRank |
1 | 424 | 128.34 |
References | Authors | |
26 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashok K. Chandra | 1 | 3116 | 1215.02 |
| Dexter C. Kozen | 2 | 5108 | 912.56 |
| Larry J. Stockmeyer | 3 | 4333 | 1077.31 |