A Problem Reduction Approach to Program Synthesis

Smith, Douglas R.

A Problem Reduction Approach to Program Synthesis

IJCAI 1983 pp. 32-36

/ijcai/1983/smith1983ijcai-problem/

Abstract

Program synthesis is the transformation of a specification of a user's problem into a computer program. A problem reduction approach to program synthesis is presented. During synthesis the user's problem is decomposed in a top-down manner into a hierarchy of subproblems. with directly solveable subproblems at the bottom. Solving these subproblems results in the bottom-up composition of a program whose structure reflects the subproblem hierarchy. The program is guaranteed to satisfy the specification and to terminate on all legal inputs. We illustrate this approach by presenting the knowledge needed to synthesize a class of divide and conquer algorithms and by deriving a Merge sort algorithm.

PDF Semantic Scholar

Cite

Text

Smith. "A Problem Reduction Approach to Program Synthesis." International Joint Conference on Artificial Intelligence, 1983.

Markdown

[Smith. "A Problem Reduction Approach to Program Synthesis." International Joint Conference on Artificial Intelligence, 1983.](https://mlanthology.org/ijcai/1983/smith1983ijcai-problem/)

BibTeX

@inproceedings{smith1983ijcai-problem,
  title     = {{A Problem Reduction Approach to Program Synthesis}},
  author    = {Smith, Douglas R.},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {1983},
  pages     = {32-36},
  url       = {https://mlanthology.org/ijcai/1983/smith1983ijcai-problem/}
}