Oriented Metrics for Bottom-Up Enumerative Synthesis DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06

Roland Meyer, Jakob Tepe · 2025

Read Oriented Metrics for Bottom-Up Enumerative Synthesis DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 by Roland Meyer, Jakob Tepe (2025) 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-2511-02491.txt.

Description

Roland Meyer and Jakob Tepe shrink the search space of program synthesis by giving programs a sense of direction. Syntax-guided synthesis hunts for a program meeting a specification, but the space of candidates is enormous. Most programs, the authors observe, are not a pile: operations such as string concatenation or bitwise conjunction transform an input into an output asymmetrically. A distance measure that respects that orientation can organise the hunt.

They develop oriented metrics for the string and bitvector domains and build four reduction techniques on them. The four prune to a ball around the target, factor the space by the equivalence the metric induces, abstract and refine that equivalence, and order the enumeration using the abstract information. A solver, generic over the choice of oriented metric, implements the package. In experiments on the domains it beat the state of the art by over tenfold.

Catalog record

CREATORRoland Meyer, Jakob Tepe
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE149 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-02491

Browse the full library · About the Tower of Babel