| Author(s): |
Brian D. Cloteaux; Desh Ranjan; |
| Title: |
Lower Bounds for Accessing Information on Pure Pointer Machines |
| Published: |
July 13, 2009 |
| Abstract: |
We study the complexity of representing an array on a Pure Pointer Machine (PPM) or a pointer machine without arithmetic capabilities. In particular, we show that lower bounds in access time for information retrieval on a PPM arise from two different factors: the amount of information being stored and the limited number of unique neighborhoods with a fixed radius that can be constructed on a PPM. This result contrasts with earlier work by Ben Amram and Galil which showed that for pointer machines with arithmetic capabilities, look-up time only depends on the amount of information stored. We then apply these bounds to show optimal look-up times for comparing elements in partial and total orders on a PPM. |
| Proceedings: |
Proceedings of the International Conference on Foundations of Computer Science |
| Pages: |
pp. 103 - 107 |
| Location: |
Las Vegas, NV |
| Dates: |
July 13-16, 2009 |
| Keywords: |
incompressibility;pointer machine;random access memory |
| Research Areas: |
Math |
| PDF version: |
 Click here to retrieve PDF version of paper (135KB) |
