POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

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.