Real-time Simulation of a Set Machine on a Ram

Abstract

The analysis of set-based programs is sometimes facilitated by the computational model of a set machine; i.e., a uniform cost sequential RAM augmented with an assortment of primitives on finite sets, under the assumption that associative operations, e.g., set membership, take unit time. In this paper we give broad sufficient conditions in which to simulate a set machine on a RAM (without set primitives) in real time. Two variants of a RAM are considered. One allows for pointer and cursor access. The other permits only pointer access. Our translation method introduces a new programming methodology for data structure design and provides a new framework for investigating automatic data structure selection for set-based programs.

Department(s)

Mathematics and Statistics

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1989 Elsevier, All rights reserved.

Publication Date

01 Jan 1989

This document is currently not available here.

Share

 
COinS