Real-time Simulation of a Set Machine on a Ram
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.
R. Paige, "Real-time Simulation of a Set Machine on a Ram," Computing and Information, Elsevier, Jan 1989.
Mathematics and Statistics
Article - Journal
© 1989 Elsevier, All rights reserved.