# E-Graph matching with monotonic tabling

**URL:** <https://swi-prolog.discourse.group/t/e-graph-matching-with-monotonic-tabling/9245>\
**Category:** General\
**Created:** [September 3, 2025, 11:50am UTC](https://swi-prolog.discourse.group/t/e-graph-matching-with-monotonic-tabling/9245 "2025-09-03T11:50:35Z")\
**Posts on this page:** 1\
**Showing post:** 4

<div class="post-metadata">

**Author:** ![kwon-young](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/kwon-young/32/4841_2.png) [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)\
**Post date:** [September 8, 2025, 2:50pm UTC](https://swi-prolog.discourse.group/t/e-graph-matching-with-monotonic-tabling/9245/4 "2025-09-08T14:50:19Z")

</div>

I am sorry to report that after a lot of experimentation with tabling, I couldn’t write an elegant version of the full congruence closure with tabling.

The problem has to do with the fact that when using tabling (so backtracking) with dynamic predicates, we need to ground the class ids.  
However, when doing congruence closure, one need to replace all uses of a class id in all pairs that uses it. For example, let’s say you have the following pairs `Node-Class`: `[a-a, f(a)-fa, f(fa)-ffa]` and you want to unify `a` and `ffa`. You need to replace every instance of `ffa` in every pairs.

Doing this is extremely slow and very tedious. Moreover, I couldn’t manage to do batch rewrites and would always get incorrect nodes.

I have written another approach based on variables for class ids that is correct and scales quite a bit better.  
I will post it when I have figured out how to make cost-based extraction to work.

---

_[View the full topic](https://swi-prolog.discourse.group/t/e-graph-matching-with-monotonic-tabling/9245)._