Space bounded computations: Review and new separation results

DOI10.1016/0304-3975(91)90391-EzbMath0745.68051OpenAlexW1974938157MaRDI QIDQ1176238

Desh Ranjan, Richard Chang, Juris Hartmanis

Publication date: 25 June 1992

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90391-e

zbMATH Keywords

demon machinesdot modellow level tape bounded computationspebble machinesspace bounded computations

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On 1-inkdot alternating Turing machines with small space ⋮ A note on multi-inkdot nondeterministic Turing machines with small space ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ Space hierarchy theorem revised. ⋮ Reversibility of computations in graph-walking automata ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ A relationship between nondeterministic turing machines and 1-inkdot turing machines with small space ⋮ Removing nondeterminism in constant height pushdown automata ⋮ Alternation for sublogarithmic space-bounded alternating pushdown automata ⋮ Factoring and Testing Primes in Small Space ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Alternating Demon Space Is Closed Under Complement and Other Simulations for Sublogarithmic Space ⋮ Bridging across the \(\log(n)\) space frontier ⋮ Unnamed Item ⋮ UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n) ⋮ Sublogarithmic $\sum _2$-space is not closed under complement and other separation results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
• Relativized circuit complexity
• Halting space-bounded computations
• Space bounds for processing contentless inputs
• Relationships between nondeterministic and deterministic tape complexities
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Parallel computation and the NC hierarchy relativized
• Classes of languages and linear-bounded automata