Relativizing Time, Space, and Time-Space

DOI10.1137/0211048zbMath0487.68038OpenAlexW2033718868MaRDI QIDQ3948590

Ronald V. Book, Meirui Xu, Christopher B. Wilson

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0211048

zbMATH Keywords

formal languagescomplexity classesrelativizationstime boundstime hierarchiesbounded queriesoracle machinesspace boundsnondeterministic acceptors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (7)

Positive relativizations for log space computability ⋮ A time-space hierarchy between polynomial time and polynomial space ⋮ Limitations of the upward separation technique ⋮ Unnamed Item ⋮ Downward translations of equality ⋮ A survey of space complexity ⋮ Finite-model theory -- A personal perspective

This page was built for publication: Relativizing Time, Space, and Time-Space