Reproduce “How to prove equations using diagrams: A categorical and operational semantics for e-graphs” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Evan Patterson
The authors give a category-theoretic semantics for valid transformations of diagrams encoding equations in e-graphs. They use initial functors, maps that preserve limits, to characterize when changes preserve represented solutions. Theorem 3.6 says weakly equivalent diagrams have naturally bijective limits under every set-valued interpretation, and conversely. The paper does not prove its listed inference motifs form a complete proof system.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.