arXiv 2206.07828
Searching Entangled Program Spaces
By James Koppel, Zheng Guo, et al.
Published 2022-06-15
Citation lineage
Review the prior work and downstream research connected to this paper.
Many problem domains, including program synthesis and rewrite-based optimization, require searching astronomically large spaces of programs. Existing approaches often rely on building specialized data structures -- version-space algebras, finite tree automata, or e-graphs -- to compactly represent these programs. To find a compact representation, existing data structures exploit independence of subterms; they blow u…