E-graphs and Equality Saturation Quiz

1. What is the main problem with traditional term rewriting?

It's too slow to compute It's destructive and forces you to commit to one path It only works with mathematical expressions It requires too much memory

2. What are the three main components of an e-graph?

Nodes, edges, and values E-classes, e-nodes, and operators Terms, expressions, and programs Patterns, substitutions, and rewrites

3. In the example (a × 2) / 2, what is the "wrong turn" that a greedy optimizer might take?

4. What makes e-graphs so space-efficient?

They compress data using algorithms They store structurally similar expressions compactly They delete old expressions when adding new ones They only store the most important expressions

5. What are the two core operations that modify an e-graph?

search and replace add and union match and substitute create and delete

6. True or False: E-graph rewriting is destructive like traditional term rewriting.

True False

7. What does it mean when an e-graph contains a cycle?

8. In the rewrite process l → r, what do you get when you search for pattern l in the e-graph?

A list of matching terms Pairs of (c, σ) where c is the matching e-class and σ is the substitution The right-hand side pattern r A new e-node to add to the graph

🧠 E-graphs & Equality Saturation Quiz