Top-down synthesis of simple divide and conquer algorithms

Loading...
Thumbnail Image
Authors
Smith, Douglas R.
Subjects
automatic programming
program synthesis
deduction
divide and conquer, top-down programming
Advisors
Date of Issue
1982-11-12
Date
1982-11-12
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
A new method is presented for the deductive synthesis of computer programs. The method takes as given a formal specification of a user's problem. The specification is allowed to be incomplete in that some or all of the input conditions may be omitted. A completed specification plus a computer program are produced by the method. Synthesis involves the top-down decomposition of the user's problem into a hierarchy of subproblems. Solving each of these subproblems results in the synthesis of a hierarchically structured program. The program is guaranteed to satisfy the completed specification and to terminate on all legal inputs. In this paper we present a framework for a top-down synthesis process, explore the structure of a class of divide and conquer algorithms, and present a method for the top-down synthesis of algorithms in this class. Detailed derivations of four sorting algorithms are presented. (Author)
Type
Technical Report
Description
Series/Report No
Department
Identifiers
NPS Report Number
NPS-52-82-011
Sponsors
supported in part by the Foundation Research Program of the Naval Postgraduate School
Funder
funds provided by the Chief of Naval Research
Format
99 p. ; 28 cm.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections