Take a sneak peek at the new NIST.gov and let us know what you think!
(Please note: some content may not be complete on the beta site.).
NIST Authors in Bold
|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|
|PDF version:||Click here to retrieve PDF version of paper (138KB)|