Joseph Y. Halpern, Lenore D. Zuck
PODC 1987
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, Lenore D. Zuck
PODC 1987
Gadi Aleksandrowicz, Hana Chockler, et al.
AAAI 2014
Joseph Y. Halpern, Mark R. Tuttle
Journal of the ACM (JACM)
Joseph Y. Halpern, Yoav Shoham
Journal of the ACM