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
Type
conference paper
DOI
10.1007/978-3-319-21668-3_12
Author(s)
Reynolds, Andrew
Deters, Morgan
Kuncak, Viktor
Tinelli, Cesare
Barrett, Clark
Date Issued

2015-07-14

Published in
Proceedings of the International Conference on Computer Aided Verification
Series title/Series vol.

Lecture Notes in Computer Science; 9207

Volume

9207

Start page

198

End page

216

Subjects

verification

•

synthesis

•

satisfiability modulo theories

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LARA  
Event nameEvent placeEvent date
International Conference on Computer Aided Verification

San Francisco

July 18-24, 2015

Available on Infoscience
June 28, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/147008
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