Hashing Modulo $\alpha$-Equivalence: Faster and Deterministic
The notion of $\alpha$-equivalence is commonly used to check if two syntax trees are identical. Maziarz, Ellis, Lawrence, Fitzgibbon, and Peyton Jones [PLDI 2021] observed that, in many applications, we would actually like to identify identical subtrees of such a tree, and designed a randomised $O(n\log^{2} n)$ time algorithm that achieves such a goal. This is certainly more appealing than the $O(n^{2})$ time obtained by direct computation, but from an algorithm designer point of view leaves open determining the best possible time complexity for this problem. Further, it would be desirable to obtain a fully deterministic algorithm. We design an $O(n\log\log n)$ time algorithm that is both significantly faster than the previously known and fully deterministic.