Relational Program Synthesis

on YouTube ↗23m

" summary

Defines relational program synthesis and builds Relish, a CEGIS-style tool that combines a compositional relational version space learner with SyGuS validation. Uses occurrence-renaming relaxation, composes finite-tree-automaton languages into hierarchical FTA that represent tuples of programs, then backtracks to enforce functional consistency. Implements encoders/decoders and comparators; on benchmarks Relish solves virtually all encoder tasks in ~20s each while EUSolver solves only half taking >10min on average, and Relish also solves more and faster on 20 StackOverflow comparator problems.

AI-written summary · about

" chapters (14)

1. 0:00Introduction
2. 1:08Relational Specification
3. 3:04Example
4. 4:41Problem Definition
5. 5:33Why is this problem challenging
6. 7:33Key Idea
7. 8:17Three Steps
8. 9:51Modular Version Space
9. 16:15Encoder Decoders
10. 17:05Experimental Results
11. 17:36Second Application Domain Synthesis
12. 18:23Results
13. 18:53Questions
14. 19:19Relational vs Syntax Guided Synthesis