Recursive Program Optimization Through Inductive Synthesis Proof Transformation

P. Madden, Alan Bundy, A. Smaill

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

The research described in this paper involved developing transformation techniques which increase the efficiency of the noriginal program, the source, by transforming its synthesis proof into one, the target, which yields a computationally more efficient algorithm. We describe a working proof transformation sys- tem which, by exploiting the duality between mathematical induction and recursion, employs the novel strategy of optimizing recursive programs by transforming inductive proofs. We compare and contrast this approach with the more traditional approaches to program transformation, and highlight the benefits of proof transformation with regards to search, correctness, automatability and generality.
Original languageEnglish
Pages (from-to)65-115
JournalJournal of Automated Reasoning
Issue number1
Publication statusPublished - 1999

Keywords / Materials (for Non-textual outputs)

  • proof transformation
  • synthesis proofs
  • induction


Dive into the research topics of 'Recursive Program Optimization Through Inductive Synthesis Proof Transformation'. Together they form a unique fingerprint.

Cite this