Syntax-guided synthesis

By Rajeev Alur, Rastislav Bodík, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, Abhishek Udupa. 2013

909 citations recorded by the source corpus.

The classical formulation of the program-synthesis problem is to find a program that meets a correctness specification given as a logical formula. Recent work on program synthesis and program optimization illustrates many potential benefits of allowing the user to supplement the logical specification with a syntactic template that constrains the space of allowed implementations. Our goal is to identify the core computational problem common to these proposals in a logical framework. The input to the syntax-guided synthesis problem (SyGuS) consists of a background theory, a semantic correctness specification for the desired program given by a logical formula, and a syntactic set of candidate implementations given by a grammar. The computational problem then is to find an implementation from the set of candidate expressions so that it satisfies the specification in the given theory. We describe three different instantiations of the counter-example-guided-inductive-synthesis (CEGIS) strategy for solving the synthesis problem, report on prototype implementations, and present experimental results on an initial set of benchmarks.

Subfields: Artificial Intelligence, Software, Natural Language Processing, Code Generation & Program Synthesis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Percy Liang
  2. Mohit Bansal
  3. Yoshua Bengio
  4. Quoc V. Le
  5. Sergey Levine
  6. Jianfeng Gao
  7. Josh Tenenbaum
  8. Graham Neubig

In Software

  1. Rishabh Singh
  2. Charles Sutton
  3. Oleksandr Polozov
  4. Dawn Song
  5. Marc Brockschmidt
  6. Pushmeet Kohli
  7. Swarat Chaudhuri
  8. Daniel Tarlow

In Natural Language Processing

  1. Rishabh Singh
  2. Dawn Song
  3. Josh Tenenbaum
  4. Charles Sutton
  5. Swarat Chaudhuri
  6. Percy Liang
  7. Xinyun Chen
  8. Oleksandr Polozov

In Code Generation & Program Synthesis

  1. Rishabh Singh
  2. Charles Sutton
  3. Swarat Chaudhuri
  4. Armando Solar-Lezama
  5. Augustus Odena
  6. Josh Tenenbaum
  7. Oleksandr Polozov
  8. Pushmeet Kohli

Citations in the corpus