Log space machines with multiple oracle tapes

DOI10.1016/0304-3975(78)90003-8zbMath0368.68058OpenAlexW1980326341MaRDI QIDQ1242686

Nancy A. Lynch

Publication date: 1978

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(78)90003-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Related Items (7)

Relativized alternation and space-bounded computation ⋮ Autoreducibility and mitoticity of logspace-complete sets for NP and other classes ⋮ Space-efficient informational redundancy ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ Relativization of questions about log space computability ⋮ A note on relativized log space ⋮ On relativizing auxiliary pushdown machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comparison of polynomial time reducibilities
• A second step toward the polynomial hierarchy
• Relationships between nondeterministic and deterministic tape complexities
• Tape bounds for time-bounded Turing machines
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relativization of questions about log space computability
• Relativization of the Theory of Computational Complexity
• Reducibility among Combinatorial Problems
• The complexity of theorem-proving procedures

This page was built for publication: Log space machines with multiple oracle tapes