Library learning compresses a given corpus of programs by extracting common structure
from the corpus into reusable library functions. Prior work on library learning suffers from two …

Query rewriting transforms a relational database query into an equivalent but more efficient
one, which is crucial for the performance of database-backed applications. Such rewriting …

Equality graphs (e-graphs) are used to compactly represent equivalence classes of terms in
symbolic reasoning systems. Beyond their original roots in automated theorem proving, e …

Many problem domains, including program synthesis and rewrite-based optimization,
require searching astronomically large spaces of programs. Existing approaches often rely …

We present egglog, a fixpoint reasoning system that unifies Datalog and equality saturation
(EqSat). Like Datalog, egglog supports efficient incremental execution, cooperating …

Rewriting is a principled term transformation technique with uses across theorem proving
and compilation. In theorem proving, each rewrite is a proof step; in compilation, rewrites …

Satisfiability Modulo Theory (SMT) solvers and equality saturation engines must generate
proof certificates from e-graph-based congruence closure procedures to enable verification …

Deep Learning (DL) is prevalently used in various industries to improve decision-making
and automate processes, driven by the ever-evolving DL libraries and compilers. The …

Rewrite rules are critical in equality saturation, an increasingly popular technique in
optimizing compilers, synthesizers, and verifiers. Unfortunately, developing high-quality …

This article presents a new compressed representation of Boolean functions, called
CFLOBDDs (for Context-Free-Language Ordered Binary Decision Diagrams). They are …