Synthesis modulo recursive functions
Authors:
Open Access
- 29 October 2013
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 407-426
Abstract
We describe techniques for synthesis and verification of recursive functional programs over unbounded domains. Our techniques build on top of an algorithm for satisfiability modulo recursive functions, a framework for deductive synthesis, and complete synthesis procedures for algebraic data types. We present new counterexample-guided algorithms for constructing verified programs. We have implemented these algorithms in an integrated environment for interactive verification and synthesis from relational specifications. Our system was able to synthesize a number of useful recursive functions that manipulate unbounded numbers and data structures.Keywords
This publication has 38 references indexed in Scilit:
- Executing Specifications Using Synthesis and Constraint Solving2013
- Software synthesis proceduresCommunications of the ACM, 2012
- Synthesis of Reactive(1) Designs2005
- Structuring Z specifications with viewsACM Transactions on Software Engineering and Methodology, 1995
- Inductive Logic Programming: Theory and methodsThe Journal of Logic Programming, 1994
- Abductive Logic ProgrammingJournal of Logic and Computation, 1992
- A Deductive Approach to Program SynthesisACM Transactions on Programming Languages and Systems, 1980
- A Methodology for LISP Program Construction from ExamplesJournal of the ACM, 1977
- Program development by stepwise refinementCommunications of the ACM, 1971
- Toward automatic program synthesisCommunications of the ACM, 1971