PLDI 2024
Mon 24 - Fri 28 June 2024 Copenhagen, Denmark
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 Jun

Displayed time zone: Windhoek change

16:00 - 17:40
4. VerificationEGRAPHS at Reykjavik
16:00
25m
Talk
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
25m
Talk
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
25m
Talk
Bridging Syntax and Semantics of Lean Expressions in E-Graphs
EGRAPHS
Marcus Rossel Technische Universität Dresden, Andrés Goens University of Amsterdam
Pre-print Media Attached
17:15
25m
Talk
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