Equivalence Hypergraphs: DPO Rewriting for Monoidal E-Graphs

Aleksei Tiurin, Chris Barrett, Dan R. Ghica +1

The technique of \emph{equality saturation}, which equips graphs with an equivalence relation, has proven effective for program optimisation. We give a categorical semantics to the…