Spring 2021

CounterExample Guided Inductive Synthesis Modulo Theories

Monday, Mar. 1, 2021 9:10 am9:40 am

Add to Calendar


Elizabeth Polgreen (University of Edinburgh)



A key principle in automated reasoning is the idea to alternate between a teacher and a learner. The learner forms hypotheses, which are incrementally refined using feedback given by the teacher. In this talk, I will discuss the importance of the vocabulary (and hence "bandwidth") of the feedback given by the teacher by looking at challenges faced by the well-known CEGIS algorithm. I will present an improved variant, called CEGIS-T, which uses expressive feedback on the syntax of potential solutions. This addresses a particular challenge for program synthesizers, namely the generation of programs that require non-trivial constants, which is out of reach for many state-of-the-art synthesizers. I will conclude with forward-looking ideas on how to elevate the syntactic feedback to semantic feedback.

PDF icon Slides7.62 MB