Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Counterexample-Guided Quantifier Instantiation for Synthesis in SMT, Computer Aided Verification
 
conference paper

Counterexample-Guided Quantifier Instantiation for Synthesis in SMT, Computer Aided Verification

Reynolds, Andrew
•
Deters, Morgan
•
Kuncak, Viktor
Show more
July 14, 2015
Proceedings of the International Conference on Computer Aided Verification
International Conference on Computer Aided Verification

We introduce the first program synthesis engine implemented inside an SMT solver. We present an approach that extracts solution functions from unsatisfiability proofs of the negated form of synthesis conjectures. We also discuss novel counterexample-guided techniques for quantifier instantiation that we use to make finding such proofs practically feasible. A particularly important class of specifications are single-invocation properties, for which we present a dedicated algorithm. To support syntax restrictions on generated solutions, our approach can transform a solution found without restrictions into the desired syntactic form. As an alternative, we show how to use evaluation function axioms to embed syntactic restrictions into constraints over algebraic datatypes, and then use an algebraic datatype decision procedure to drive synthesis. Our experimental evaluation on syntax-guided synthesis benchmarks shows that our implementation in the CVC4 SMT solver is competitive with state-of-the-art tools for synthesis.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

ReynoldsETAL15CegisSMT.pdf

Access type

openaccess

Size

363.64 KB

Format

Adobe PDF

Checksum (MD5)

3dcd2ea825df4c888b6a7cdf7ab9a655

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés