A Problem Reduction Approach to Program Synthesis

Smith, Douglas R.

A Problem Reduction Approach to Program Synthesis

Download BibTeX Cite

Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Automatic Programming. Pages 32-35.

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 Mergesort algorithm.

Douglas R. Smith. 1983. A Problem Reduction Approach to Program Synthesis. In Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83. IJCAI, 32–35. https://ijcai.org/proceedings/1983/7

@inproceedings{ijcai1983p7,
  title     = {A Problem Reduction Approach to Program Synthesis},
  author    = {Smith, Douglas R.},
  booktitle = {Proceedings of the Eighth International Joint Conference on
               Artificial Intelligence, {IJCAI-83}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Alan Bundy},
  pages     = {32--35},
  year      = {1983},
  note      = {Automatic Programming},
  url       = {https://ijcai.org/proceedings/1983/7},
}

TY  - CPAPER
TI  - A Problem Reduction Approach to Program Synthesis
AU  - Smith, Douglas R.
T2  - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1983
SP  - 32
EP  - 35
UR  - https://ijcai.org/proceedings/1983/7
ER  -