Michael C. Loui, Anne Condon, et al.
ACM Computing Surveys
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.
Michael C. Loui, Anne Condon, et al.
ACM Computing Surveys
Joseph Y. Halpern, Moshe Y. Vardi
STOC 1988
Joseph Y. Halpern
Journal of Philosophical Logic
Ronald Fagin, Joseph Y. Halpern, et al.
Journal of the ACM