Statements (28)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:abbreviation |
ATM
|
| gptkbp:acceptsInputIf |
all computation paths accept (universal)
there exists a computation tree with an accepting path (existential) |
| gptkbp:characterizesComplexityClass |
gptkb:PSPACE
AP (alternating polynomial time) |
| gptkbp:complexity |
gptkb:AP
gptkb:AL |
| gptkbp:definedIn |
polynomial hierarchy
alternating space complexity classes |
| gptkbp:describedBy |
gptkb:Journal_of_the_ACM
|
| gptkbp:generalizes |
deterministic Turing machines
nondeterministic Turing machines |
| gptkbp:hasKeyProperty |
can alternate between existential and universal states
|
| gptkbp:hasStateType |
existential state
universal state |
| https://www.w3.org/2000/01/rdf-schema#label |
alternating Turing machines
|
| gptkbp:introduced |
gptkb:Dexter_Kozen
Ashok K. Chandra Larry J. Stockmeyer |
| gptkbp:introducedIn |
1976
|
| gptkbp:relatedTo |
gptkb:quantified_Boolean_formula
parallel computation Boolean circuit complexity |
| gptkbp:studiedIn |
theoretical computer science
|
| gptkbp:usedIn |
gptkb:complexity_theory
|
| gptkbp:bfsParent |
gptkb:Larry_Stockmeyer
|
| gptkbp:bfsLayer |
6
|