On time versus space III
From MaRDI portal
Publication:3745280
Recommendations
- Hierarchies and space measures for pointer machines
- The complexity of on-line simulations between multidimensional turing machines and random access machines
- Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
- On pointers versus addresses
- scientific article; zbMATH DE number 177809
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3471609 (Why is no real title available?)
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- A class of algorithms which require nonlinear time to maintain disjoint sets
- A general class of resource tradeoffs
- A space bound for one-tape multidimensional Turing machines
- On Time Versus Space
- On time versus space. II
- Relations Between Time and Tape Complexities
- Space-bounded simulation of multitape turing machines
- Speedups of deterministic machines by synchronous parallel machines
- Storage Modification Machines
- Tape bounds for time-bounded Turing machines
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
Cited in
(9)- The problem of space invariance for sequential machines
- Space measures for storage modification machines
- Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
- The complexity of on-line simulations between multidimensional turing machines and random access machines
- Optimal On-Line Simulations of Tree Machines by Random Access Machines
- Time and space measures for a complete graph computation model
- Three Studies in the Philosophy of Space and Time
- Limited relativity. Book 3
- Parallelizing time with polynomial circuits
This page was built for publication: On time versus space III
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3745280)
