Top-down synthesis of divide-and-conquer algorithms

DOI10.1016/0004-3702(85)90083-9zbMath0573.68053OpenAlexW2045323411MaRDI QIDQ1062770

Douglas R. Smith

Publication date: 1985

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(85)90083-9

zbMATH Keywords

sortingprogram synthesisquicksortmergesortproblem reductionderivation of algorithms from a formal specification of a problemhierarchy of specifications for subproblems

Mathematics Subject Classification ID

Searching and sorting (68P10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Theory of software (68N99)

Related Items

Categories, relations and dynamic programming ⋮ A sheaf-theoretic approach to pattern matching and related problems ⋮ A higher-order interpretation of deductive tableau ⋮ Deductive synthesis of sorting programs ⋮ An abstract formalization of correct schemas for program synthesis ⋮ Automatic programming: A tutorial on formal methodologies ⋮ Top-down synthesis of divide-and-conquer algorithms ⋮ Deductive and inductive synthesis of equational programs ⋮ Constructing specification morphisms ⋮ Logic program synthesis from incomplete specifications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The design of divide and conquer algorithms
• Justification of the structural synthesis of programs
• Top-down synthesis of divide-and-conquer algorithms
• Non-resolution theorem proving
• A synthesis of several sorting algorithms
• Synthesis: Dreams → Programs
• Algorithm classification through synthesis
• Program Development as a Formal Activity
• A Deductive Approach to Program Synthesis
• A Transformation System for Developing Recursive Programs