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. Journal articles
  4. Refutation-based synthesis in SMT
 
research article

Refutation-based synthesis in SMT

Reynolds, Andrew  
•
Kuncak, Viktor  
•
Tinelli, Cesare
Show more
December 1, 2019
Formal Methods In System Design

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.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s10703-017-0270-2
Web of Science ID

WOS:000517122100001

Author(s)
Reynolds, Andrew  
Kuncak, Viktor  
Tinelli, Cesare
Barrett, Clark
Deters, Morgan
Date Issued

2019-12-01

Publisher

SPRINGER

Published in
Formal Methods In System Design
Volume

55

Issue

2

Start page

73

End page

102

Subjects

Computer Science, Theory & Methods

•

Computer Science

•

program synthesis

•

satisfiability modulo theories

•

automated deduction

•

quantifier elimination

•

abstraction

•

sat

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LARA  
Available on Infoscience
March 13, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/167262
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