Pointer Machines and Pointer Algorithms: an Annotated Bibliography

The term pointer machine has been used ambiguously in Computer Science literature. In this report we give precise definitions of several models that have been referred to as "pointer machines" and list references for each of these models under the appropriate heading. 1 Introduction In a 1992 paper by Galil and the author we referred to a "pointer machine" model of computation. A subsequent survey of related literature has produced over thirty references to papers having to do with "pointer machines", naturally containing a large number of cross-references. These papers address a range of subjects that range from the model considered in the above paper to some other ones which are barely comparable. The fact that such different notions have been discussed under the heading of "pointer machines" has produced the regrettable effect that cross references are sometimes found to be misleading. Clearly, it is easy for a reader who does not follow a paper carefully to misinterpret its claims..