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.

Authors

• Steven Lindell

Keywords

No keywords are indexed for this paper.