On time versus space III

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 computational models, including pointer machines, which model computations on graphs and data structures. Every pointer machine of time complexity T(n) can be simulated by a pointer machine of space complexity O(T(n)/log T(n)). © 1986 Springer-Verlag New York Inc.