On time versus space III

DOI10.1007/BF01704903zbMATH Open0606.68043MaRDI QIDQ3745280FDOQ3745280

Authors: Joseph Y. Halpern, Albert R. Meyer, Daniel Weise, Michael C. Loui 

Publication date: 1986

Published in: Mathematical Systems Theory (Search for Journal in Brave)

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

zbMATH Keywords

graphsdata structuresspace complexitytime complexitypointer machinesrandom access machinesspace reductionmultidimensional Turing machinesspace efficient simulations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• A class of algorithms which require nonlinear time to maintain disjoint sets
• Title not available (Why is that?)
• A general class of resource tradeoffs
• Storage Modification Machines
• Speedups of deterministic machines by synchronous parallel machines
• On Time Versus Space
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Title not available (Why is that?)
• On time versus space. II
• Tape bounds for time-bounded Turing machines
• Relations Between Time and Tape Complexities
• Space-bounded simulation of multitape turing machines
• A space bound for one-tape multidimensional Turing machines

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)