On time versus space III
From MaRDI portal
Publication:3745280
DOI10.1007/BF01704903zbMath0606.68043MaRDI QIDQ3745280
Joseph Y. Halpern, Albert R. Meyer, Daniel Weise, Michael C. Loui
Publication date: 1986
Published in: Mathematical Systems Theory (Search for Journal in Brave)
graphsdata structurestime complexityspace complexitypointer machinesrandom access machinesspace reductionmultidimensional Turing machinesspace efficient simulations
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (3)
Space measures for storage modification machines ⋮ Parallelizing time with polynomial circuits ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- A class of algorithms which require nonlinear time to maintain disjoint sets
- Speedups of deterministic machines by synchronous parallel machines
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- A space bound for one-tape multidimensional Turing machines
- On time versus space. II
- A general class of resource tradeoffs
- Tape bounds for time-bounded Turing machines
- Storage Modification Machines
- Space-bounded simulation of multitape turing machines
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- On Time Versus Space
- Relations Between Time and Tape Complexities
This page was built for publication: On time versus space III
