Program Synthesis with Equivalence Reduction
We introduce program synthesis with equivalence reduction, a synthesis methodology that utilizes relational specifications over components of a given synthesis domain to reduce the search space. Leveraging a blend of classic and modern techniques from term rewriting, we use relational specifications to discover a canonical representative per equivalence class of programs. We show how to design synthesis procedures that only consider programs in normal form, thus pruning the search space. We discuss how to implement equivalence reduction using efficient data structures, and demonstrate the significant reductions it can achieve in synthesis time.
Tue 15 Jan
|11:00 - 11:30|
|Link to publication DOI Pre-print File Attached|
|11:30 - 12:00|
|12:00 - 12:30|