8 papers · 1 filter
Efficient Cost Bounds with Linear Maps
David M Kahn, Jan Hoffmann, Thomas Reps +1
The Automatic Amortized Resource Analysis (AARA) derives program-execution cost bounds using types. To do so, AARA often makes use of cost-free types, which are critical for the co…
Semantics of Sets of Programs
Jinwoo Kim, Shaan Nagy, Thomas Reps +1
Applications like program synthesis sometimes require proving that a property holds for all of the infinitely many programs described by a grammar - i.e., an inductively defined se…
Verifying Solutions to Semantics-Guided Synthesis Problems
Charlie Murphy, Keith Johnson, Thomas Reps +1
Semantics-Guided Synthesis (SemGuS) provides a framework to specify synthesis problems in a solver-agnostic and domain-agnostic way, by allowing a user to provide both the syntax a…
Synthesizing Formal Semantics from Executable Interpreters
Jiangyi Liu, Charlie Murphy, Anvay Grover +3
Program verification and synthesis frameworks that allow one to customize the language in which one is interested typically require the user to provide a formally defined semantics…
Automating Pruning in Top-Down Enumeration for Program Synthesis Problems with Monotonic Semantics
Keith J. C. Johnson, Rahul Krishnan, Thomas Reps +1
In top-down enumeration for program synthesis, abstraction-based pruning uses an abstract domain to approximate the set of possible values that a partial program, when completed, c…
Automating Unrealizability Logic: Hoare-Style Proof Synthesis for Infinite Sets of Programs
Shaan Nagy, Jinwoo Kim, Thomas Reps +1
Automated verification of all members of a (potentially infinite) set of programs has the potential to be useful in program synthesis, as well as in verification of dynamically loa…