Samuel R. Buss.
"Alogtime algorithms for tree isomorphism, comparison and canonization."
In Computational Logic and Proof Theory, Proceedings 5th Gödel Colloquium '97.
Lecture Notes in Computer Science #1289
Springer-Verlag, Berlin, 1997, pp. 18-33.
Download article: postscript or PDF.
Abstract: The tree isomorphism problem is the problem of determining whether two trees are isomorphic. The tree canonization problem is the problem of producing a canonical tree isomorphic to a given tree. The tree comparison problem is the problem of determining whether one tree is less than a second tree in a natural ordering on trees. We present alternating logarithmic time algorithms for the tree isomorphism problem, the tree canonization problem and the tree comparison problem. As a consequence, there is a recursive enumeration of the alternating log time tree problems.
Back to Sam Buss's publications page.