Talks
Spring 2021

Neural Network guided Grammar Filtering For Syntax-Guided Synthesis

Monday, Mar. 1, 2021 10:20 am10:25 am

Add to Calendar

Speaker: 

Mark Santolucito (Barnard College)

Location: 

Zoom

Programming-by-example (PBE) is a synthesis paradigm that allows users to generate functions by simply providing input-output examples. While a promising interaction paradigm, synthesis is still too slow for real-time interaction and more widespread adoption. Existing approaches to PBE synthesis have used automated reasoning tools, such as SMT solvers, as well as machine learning techniques. At its core, the automated reasoning approach relies on highly domain-specific knowledge of programming languages. On the other hand, the machine learning approaches utilize the fact that when working with program code, it is possible to generate arbitrarily large training datasets. In this work, we propose a system for using machine learning in tandem with automated reasoning techniques to solve Syntax Guided Synthesis (SyGuS) style PBE problems. By preprocessing SyGuS PBE problems with a neural network, we can use a data-driven approach to reduce the size of the search space, then allow automated reasoning-based solvers to more quickly find a solution analytically. Our system is able to run atop existing SyGuS PBE synthesis tools, decreasing the runtime of the winner of the 2019 SyGuS Competition (CVC4) for the PBE Strings track by 47.65% to outperform all of the competing tools.

AttachmentSize
PDF icon Slides317.86 KB