Joseph Y. Halpern
Information and Control
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.
Joseph Y. Halpern
Information and Control
Joseph Y. Halpern, Ronald Fagin
PODC 1985
Yoram Moses, Danny Dolev, et al.
Distributed Computing
Ronald Fagin, Joseph Y. Halpern, et al.
FOCS 1984