No label defined (Q3787475)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4050986
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4050986 |
Statements
1988
0 references
complexity theory
0 references
alternating auxiliary pushdown hierarchy
0 references
machine model
0 references
logarithmic alternation hierarchy
0 references
pushdown store
0 references
PSPACE
0 references
pushdown automata with unbounded alternation
0 references
0.8459188938140869
0 references
0.8381026387214661
0 references
0.8314438462257385
0 references
0.8311141133308411
0 references
[For the entire collection see Zbl 0635.00015.] An alternating auxiliary pushdown hierarchy is defined by extending the machine model of the logarithmic alternation hierarchy by a pushdown store while keeping a polynomial time bound. Although recently it was proven by Borodin et al. that the class of languages accepted by nondeterministic logarithmic space bounded auxiliary pushdown automata with a polynomial time bound is closed under complement, it is shown that, surprisingly, the further levels of this alternating auxiliary pushdown hierarchy coincide level by level with the polynomial hierarchy. Furthermore, it is shown that PSPACE can be characterized by simultaneously logarithmic space and polynomial time bounded auxiliary pushdown automata with unbounded alternation.
0 references