Larry Stockmeyer, Albert R. Meyer
Journal of the ACM
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.
Larry Stockmeyer, Albert R. Meyer
Journal of the ACM
Albert R. Meyer, Arnold L. Rosenberg, et al.
SWAT 1967
Joseph Y. Halpern, Yoram Moses, et al.
STOC 1988
Ronald Fagin, Joseph Y. Halpern, et al.
Information and Computation