A logspace algorithm for tree canonization (1992)

---

Link: https://dl.acm.org/doi/10.1145/129712.129750

Abstract: We present a solution to the problem of assigning to each directed tree $T$ of size $n$ a unique isomorphism invariant name for $T$, using only work space $O(\log n)$. Hence, tree isomorphism is computable in logspace. As another consequence, we obtain the corollary that the set of logspace computable queries ($Lspace$) on trees is recursively enumerable. Our results extend easily to undirected trees and even forests.

---