# Abstract Interpretation on E-Graphs

arXiv: https://arxiv.org/abs/2203.09191 · HTML: https://mlsanity.com/paper/2203.09191/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 12 references that are in the map.
- First posted on arXiv 17 Mar 2022.

## Builds on (most cited first, 2 of 2)

- [Rewrite Rule Inference Using Equality Saturation](https://mlsanity.com/paper/2108.10436/) (2021)
- [SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra](https://mlsanity.com/paper/2002.07951/) (2020)

## Abstract (arXiv)

Recent e-graph applications have typically considered concrete semantics of expressions, where the notion of equivalence stems from concrete interpretation of expressions. However, equivalences that hold over one interpretation may not hold in an alternative interpretation. Such an observation can be exploited. We consider the application of abstract interpretation to e-graphs, and show that within an e-graph, the lattice meet operation associated with the abstract domain has a natural interpretation for an e-class, leading to improved precision in over-approximation. In this extended abstract, we use Interval Arithmetic (IA) to illustrate this point.