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

Abstract

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 search problems. Within this domain transformations for converting solutions of simple searching problems to solutions of more complex problems have been developed. 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 already been used to develop a number of new algorithms, and it represents a new level of generality in software engineering tools.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1978
Accession Number
ADA066897

Entities

People

  • Jon Bentley
  • Mary Shaw

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Concrete
  • Construction
  • Databases
  • Efficiency
  • Engineering
  • Military Research
  • Sequences
  • Software Development
  • Specifications
  • Trees (Data Structures)
  • Verification

Fields of Study

  • Computer science
  • Engineering

Readers

  • Calculus or Mathematical Analysis
  • Systems Analysis and Design