Carnegie Mellon University
Browse

An Alphard Specification of a Correct and Efficient Transformation on Data Structures

journal contribution
posted on 1979-01-01, 00:00 authored by Jon Louis Bentley, Mary Shaw

In this paper we study standard program components applicable to a wide variety of design tasks; we choose for this study the specific problem domain of data structures for general searching problems, Within this domain Bentley and Saxe (1978) have developed transformations for converting solutions of simple searching problems to solutions of more complex problems. We discuss one of those transformations, specify precisely the transformation and its conditions of applicability, and prove its correctness; we accomplish this by casting it in terms of abstract data types -- specifically by using the Alphard form mechanism. We also demonstrate that the costs of the structures derived by this transformation are only slightly greater than the costs of the original solutions. The transformation we describe has alrwady been used to develop a number of new algorithms, and it represents a new level of generality in software engineering tools.

History

Date

1979-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC