What is a “pointer machine”?

ABSTRACT

A "Pointer Machine" is many things. Authors who consider referring to this term are invited to read the following note first.

REFERENCES

• 1: [1] A. M. Ben-Amram, "On the power of random access machines," thesis, Tel-Aviv University, 1994.
• 2: Amir M. Ben-Amram , Zvi Galil, On pointers versus addresses, Journal of the ACM (JACM), v.39 n.3, p.617-648, July 1992 [doi>10.1145/146637.146666]
• 3: [3] Y. Gurevich, "Kolmogorov machines and related issues: the column on Logic in Computer Science," Bull. of the EATCS 35 (1988), 71-82.
• 4: Zvi Galil , Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys (CSUR), v.23 n.3, p.319-344, Sept. 1991 [doi>10.1145/116873.116878]
• 5: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 6: Neil D. Jones, Constant time factors do matter, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.602-611, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167244]
• 7: [7] D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass. 1968, 1973.
• 8: [8] A. N. Kolmogorov and V. A. Uspenskii, "On the definition of an algorithm," Uspehi Mat. Nauk. 13 (1958), 3-28. English translation in AMS transl. II Vol. 29 (1963), 217-245.
• 9: [9] R. Paige, "Real-time simulation of a set machine on a RAM," in Computing and Information ICCI '89, Vol. 2, R. Janicki and W. Koczkodaj (eds.), 1989.
• 10: [10] A. Schönhage, "Storage modification machines," SIAM J. Comput. 9:3 (1980), 490-508.
• 11: [11] K. V. Shvachko, "Different Modifications of Pointer Machines and their Computational Power," Proc. Symp. Mathematical Foundations of Computer Science (MFCS) 1991, LNCS 520, Springer, Berlin, 426-435.
• 12: [12] R. E. Tarjan, "A class of algorithms which require nonlinear time to maintain disjoint sets," J. Comput. System Sci. 18 (1979), 110-127.
• 13: Peter van Emde Boas, Machine models and simulations, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory