Top-down synthesis of divide-and-conquer algorithms
type: Item
instance of: scholarly article
title: Top-down synthesis of divide-and-conquer algorithms
zbMATH Open document ID: 0573.68053
DOI: 10.1016/0004-3702(85)90083-9
author: Douglas R. Smith
published in: Artificial Intelligence
publication date: 1985-01-01T00:00:00Z
review text: A top-down method is presented for the derivation of algorithms from a formal specification of a problem. This method has been implemented in a system called CYPRESS. The synthesis process involves the top-down decomposition of the initial specification into a hierarchy of specifications for subproblems. Synthesizing programs for each of these subproblems results in the composition of a hierarchically structured program. The initial specification is allowed to be partial in that some or all of the input conditions may be missing. CYPRESS completes the specification and produces a totally correct applicative program. Much of CYPRESS' knowledge comes in the form of 'design strategies' for various classes of algorithms. The structure of a class of divide-and-conquer algorithms is explored and provides the basis for several design strategies. Detailed derivations of mergesort and quicksort algorithms are presented.
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68N99
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 3915660
zbMATH Keywords: sorting
zbMATH Keywords: program synthesis
zbMATH Keywords: problem reduction
zbMATH Keywords: derivation of algorithms from a formal specification of a problem
zbMATH Keywords: hierarchy of specifications for subproblems
zbMATH Keywords: mergesort
zbMATH Keywords: quicksort
MaRDI profile type: Publication
full work available at URL: 0004-3702(85)90083-9
OpenAlex ID: W2045323411
cites work: Q3948568
cites work: Non-resolution theorem proving
cites work: Program Development as a Formal Activity
cites work: A Transformation System for Developing Recursive Programs
cites work: Algorithm classification through synthesis
cites work: A synthesis of several sorting algorithms
cites work: Q3783490
cites work: Synthesis: Dreams → Programs
cites work: A Deductive Approach to Program Synthesis
cites work: Justification of the structural synthesis of programs
cites work: Q3939266
cites work: The design of divide and conquer algorithms
description: scientific article; zbMATH DE number 3915660