Recursive Program Synthesis from Sketches and Mixed-Quantifier Properties

Derek Egolf, Stavros Tripakis · 2026

Read Recursive Program Synthesis from Sketches and Mixed-Quantifier Properties by Derek Egolf, Stavros Tripakis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04045.txt.

Description

Derek Egolf and Stavros Tripakis present a method to build recursive programs from logical rules that mix quantifiers. Their method starts from a sketch, an outline of the wanted program, and fills it in by search. Counterexamples guide the search away from wrong candidates.

The pair's algorithm learns syntax limits from each counterexample, which prunes the space of candidates. A second pruning trick blocks invalid candidates before they are even listed. Their tool, Cataclyst, solves nearly all of a suite of sixty test cases. Versions without either pruning idea solve fewer. The only other tool that handles such mixed rules lacks sketching and solves far fewer cases in the suite.

Catalog record

CREATORDerek Egolf, Stavros Tripakis
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-04045

Browse the full library · About the Tower of Babel