On relativizing auxiliary pushdown machines

DOI10.1007/BF01744301MaRDI QIDQ3862402zbMATH OpenOpenAlexFDO

Authors Dana Angluin

Publication date 1980

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01744301

zbMATH Keywords

auxiliary pushdown machinescomputational complexity classes relative to oracle setsoracle Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• Bounded query machines: on NP and PSPACE
• Bounded query machines: on NP( ) and NPQUERY( )
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Log space machines with multiple oracle tapes
• On the Tape Complexity of Deterministic Context-Free Languages
• Relativization of questions about log space computability
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

Cited in

(7)

• Consistency in nondeterministic storage
• Space-bounded hierarchies and probabilistic computations
• 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

This page was built for publication: On relativizing auxiliary pushdown machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3862402)