On relativizing auxiliary pushdown machines
From MaRDI portal
Publication:3862402
DOI10.1007/BF01744301zbMath0426.68023OpenAlexW2007710676MaRDI QIDQ3862402
Publication date: 1980
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01744301
oracle Turing machinesauxiliary pushdown machinescomputational complexity classes relative to oracle sets
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
Relativized alternation and space-bounded computation ⋮ A measure of relativized space which is faithful with respect to depth ⋮ A survey of space complexity ⋮ Properties of probabilistic pushdown automata ⋮ Properties of probabilistic pushdown automata ⋮ Consistency in nondeterministic storage ⋮ Space-bounded hierarchies and probabilistic computations
Cites Work
- Bounded query machines: on NP and PSPACE
- Bounded query machines: on NP( ) and NPQUERY( )
- Log space machines with multiple oracle tapes
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativization of questions about log space computability
- On the Tape Complexity of Deterministic Context-Free Languages
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
This page was built for publication: On relativizing auxiliary pushdown machines
