Anders Ågren Thuné, Johannes Borgström, Lars-Henrik Eriksson, John Högberg, Tjark Weber, and Tobias Wrigstad. Extended abstract, EGRAPHS 2026.
To represent the possible conditionally optimised versions of a program term, we define predicate e-graphs as an extension of coloured e-graphs. In predicate e-graphs: 1) Colours are associated with sets of Boolean terms denoting assumptions, and the directed graph structure on colours is compatible with the implication structure on these sets. 2) Colours form a rooted directed graph instead of a tree, meaning that one colour can have multiple direct "parents". 3) The directed graph structure can add edges dynamically. 4) Colours can be identified, requiring the corresponding e-graphs to be merged and identified. This extended abstract articulates the core ideas, invariants, and operations of the model.