a logspace algorithm for tree canonization (extended 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.
log algorithm tree tree abstraction direct size invariance space queries trees