The problem of space invariance for sequential machines
From MaRDI portal
Publication:1102112
DOI10.1016/0890-5401(88)90052-1zbMath0643.68055OpenAlexW2001623513MaRDI QIDQ1102112
Cees Slot, Peter van Emde Boas
Publication date: 1988
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(88)90052-1
space efficiencyinvariance thesisperfect hashingsimulation of RAM's by Turing machinesspace measures for RAM
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (7)
Invariance properties of RAMs and linear time ⋮ A theory of strict P-completeness ⋮ The complexity of on-line simulations between multidimensional turing machines and random access machines ⋮ A survey of space complexity ⋮ Sorting, linear time and the satisfiability problem ⋮ A theory of strict P-completeness ⋮ Time-space tradeoffs for satisfiability
Cites Work
- Two results on tables
- Space measures for storage modification machines
- Halting space-bounded computations
- A characterization of the power of vector machines
- Time bounded random access machines
- Relationships between nondeterministic and deterministic tape complexities
- Why Gödel didn't have church's thesis
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Fast Simulation of Turing Machines by Random Access Machines
- Storage Modification Machines
- Should Tables Be Sorted?
- Alternation
- A universal interconnection pattern for parallel computers
- Time Bounded Random Access Machines with Parallel Processing
- Observations About the Development of Theoretical Computer Science
- Origins of Recursive Function Theory
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The problem of space invariance for sequential machines
