Journal article:

    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.