LCS Publication Details
Publication Title: ON TIME VERSUS SPACE III
Publication Author: Meyer, Albert, R.
Additional Authors: Weise, Daniel and Loui, Michael C.
LCS Document Number: MIT-LCS-TM-175
Publication Date: 9-1-1980
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
Paul and Reischuk devised space efficient simulations of logarithmic cost random access machines and multidimensional Turing machines. We simplify their general space reduction technique and extend it to other models of computation, particularly to the class of storage modification machines (SMM), a model of list processing. Every SMM of time complexity t(n) can be simulated by an SMM of space complexity t(n)/log t(n).
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.