The problem of space invariance for sequential machines

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

zbMATH Keywords

space efficiencyinvariance thesisperfect hashingsimulation of RAM's by Turing machinesspace measures for RAM

Mathematics Subject Classification ID

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