Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Lower Bounds for Accessing Information on Pure Pointer Machines

Published

Author(s)

Brian D. Cloteaux, Desh Ranjan

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 Title
Proceedings of the International Conference on Foundations of Computer Science
Conference Dates
July 13-16, 2009
Conference Location
Las Vegas, NV

Keywords

incompressibility, pointer machine, random access memory

Citation

Cloteaux, B. and Ranjan, D. (2009), Lower Bounds for Accessing Information on Pure Pointer Machines, Proceedings of the International Conference on Foundations of Computer Science, Las Vegas, NV, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=51268 (Accessed April 18, 2024)
Created July 13, 2009, Updated February 19, 2017