Conference item
Counterexample guided inductive synthesis modulo theories
- Abstract:
- Program synthesis is the mechanised construction of software. One of the main difficulties is the efficient exploration of the very large solution space, and tools often require a user-provided syntactic restriction of the search space. We propose a new approach to program synthesis that combines the strengths of a counterexample-guided inductive synthesizer with those of a theory solver, exploring the solution space more efficiently without relying on user guidance. We call this approach CEGIS(T ), where T is a first-order theory. In this paper, we focus on one particular challenge for program synthesizers, namely the generation of programs that require non-trivial constants. This is a fundamentally difficult task for state-of-the-art synthesizers. We present two exemplars, one based on Fourier-Motzkin (FM) variable elimination and one based on firstorder satisfiability. We demonstrate the practical value of CEGIS(T ) by automatically synthesizing programs for a set of intricate benchmarks.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 596.0KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-319-96145-3_15
Authors
- Publisher:
- Springer Verlagr
- Host title:
- 30th International Conference on Computer Aided Verification, July 14-17, 2018, Oxford, UK
- Journal:
- Computer Aided Verification More from this journal
- Pages:
- 270-288
- Series:
- Lecture Notes in Computer Science
- Publication date:
- 2018-07-18
- Acceptance date:
- 2018-03-31
- DOI:
- ISBN:
- 9783319961453
- Pubs id:
-
pubs:835822
- UUID:
-
uuid:033d5ad5-2d93-4399-bb7c-e3031f22c755
- Local pid:
-
pubs:835822
- Source identifiers:
-
835822
- Deposit date:
-
2018-04-16
Terms of use
- Copyright holder:
- © Abate, et al 2018
- Copyright date:
- 2018
- Notes:
-
This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License(http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record