Divide-and-Conquer Algorithms for Synthesis

This project aims to produce more efficient algorithms for program synthesis using techniques that decompose the task at hand into simpler tasks. Here, instances of the program synthesis problem are solved by finding smaller sub-solutions that are correct for subsets of the input space and then recombining them into a full correct solution. The tool EUSolver which was the outcome of this project won the general track at the Syntax Guided Synthesis (SyGuS) competitions in 2016 and 2017, and the programming-by-example track in 2016. The tool is available at https://bitbucket.org/abhishekudupa/eusolver/ (opens in new tab)