PLDI 2024 (series) / EGRAPHS 2024 (series) / EGRAPHS 2024 /
Automated Proof Generation for Associative and Distributive Rewriting with E-Graphs
Mon 24 Jun 2024 16:00 - 16:25 at Reykjavik - 4. Verification
We present a strategy for encoding a dependently-typed inductive language originally designed for a proof assistant within e-graphs. This language necessitates automated reasoning about distributivity and associativity. We encode our domain-specific language into egglog. Since egglog currently lacks proof extraction, we discuss strategies for building proof trees within egglog and approaches to implementing proof extraction in Metatheory.jl. Once extraction exists, we plan on interfacing with Coq to automate proof generation and checking. Having such a tool would drastically reduce the overhead in using our Coq library and enable reasoning about distributive and associative structures more broadly.
Mon 24 JunDisplayed time zone: Windhoek change
Mon 24 Jun
Displayed time zone: Windhoek change
16:00 - 17:40 | |||
16:00 25mTalk | Automated Proof Generation for Associative and Distributive Rewriting with E-Graphs EGRAPHS Adrian Lehmann University of Chicago, Ben Caldwell University of Chicago, John Reppy University of Chicago, USA, Robert Rand University of Chicago Media Attached | ||
16:25 25mTalk | superVer: Verifying Probabilistic Independence of Systems of Expressions using Equality Saturation EGRAPHS Alexander Treff University of Lübeck, Pajam Pauls University of Lübeck, Maximilian Orlt TU Darmstadt, Marc Gourjon Hamburg University of Technology and NXP Semiconductors Germany GmbH Media Attached | ||
16:50 25mTalk | Bridging Syntax and Semantics of Lean Expressions in E-Graphs EGRAPHS Pre-print Media Attached | ||
17:15 25mTalk | Disequalities in E-Graphs: An Experiment EGRAPHS George Zakhour University of St. Gallen, Pascal Weisenburger University of St. Gallen, Guido Salvaneschi University of St. Gallen Pre-print Media Attached |