Alogtime Algorithms forTree Isomorphism, Comparison, and CanonizationSamuel R. Buss?Departments of Mathematics & Computer Science,Univ. of California, San Diego,La Jolla, CA 92093-0112Abstract. The tree isomorphism problem is the problem of determiningwhether two trees are isomorphic. The tree canonization problem isthe problem of producing a canonical tree isomorphic to a giventree. The tree comparison problem is the problem of determiningwhether one tree is less than a second tree in a natural orderingon trees. We present alternating logarithmic time algorithms for thetree isomorphism problem, the tree canonization problem and the treecomparison problem. As a consequence, there is a recursive enumerationof the alternating log time tree problems.1 IntroductionA tree is a finite, connected, acyclic graph with a distinguished root node. Anisomorphism between two trees T1and T2is a bijection between the nodesof T1and the nodes of T2which preserves the edges and which maps the rootof T1to the root of T2. Two trees are isomorphic if there is an isomorphismbetween them.An implicit component of our definition of “isomorphism” is that the childrenof a node in a tree are unordered. Of course, whenever a tree is drawn, orespecially, is represented in on a computer, there is an ordering specified bythe representation of the tree. For instance, we define a string representationof trees below, and any string representation of a tree orders the subtrees andnodes of T . This means of course that a given tree may have many differentrepresentations. The question of whether two different string representations arerepresentations of the same tree is called the tree isomorphism problem. Oneway to solve the isomorphism is define canonical representations for trees insuch way that every (unordered) tree has exactly one canonical representations.The problem of converting an arbitrary string representation of a tree into acanonical representation is called the tree canonization problem.In addition to the tree isomorphism and tree canonization problems, we willconsider the tree comparison problem. Below we define a linear ordering, ≺,ontrees: the tree comparison problem is the problem of, given string representationsof two trees, to determine whether the first tree is less than (≺) the second.?Supp orted in part by NSF grants DMS-9503247 and DMS-9205181.The main results of this paper give alternating logtime (Alogtime) algorithmsfor the tree isomorphism, tree comparison and tree canonization problems. Therehave been several prior related results. First, Aho-Hopcroft-Ullman[1] gave alinear time algorithm for tree isomorphism, based on comparing two trees ina bottom-up fashion. Obviously, linear time is the best possible sequential runtime for tree isomorphism, but it is possible to consider refined algorithms insmaller complexity classes, where one restricts the circuit depth, the paralleltime, or the Turing machine space usage. Recall that the complexity class NCis the class of predicates solvable by polynomial size, polylog depth circuits; asis well known, uniform NC algorithms are exactly the algorithms that can besolved on PRAM’s in polylogarithmic time with polynomially many processors.Ruzzo [13] mentions an NC-algorithm for solving the tree isomorphism problemfor trees of logarithmic degree. Miller and Reif [12] later gave an NC-algorithmfor solving the tree isomorphism and tree canonization problems for trees ofarbitrary degree and depth, based on tree-contraction methods. Finally, in thebest prior result, Lindell [8] gave deterministic logarithmic space algorithms forthe tree isomorphism, tree comparison and tree canonization problems. It wasthe logarithmic space algorithms that motivated the work of this paper to givealternating logarithmic time algorithms for these algorithms.One application of the Alogtime algorithms presented in this paper is toa question that arises from finite model theory. One would like to consideralgorithms that compute intrinsic properties of trees, which do not depend onthe particular representation of the trees. Let C be a natural complexity classcontaining Alogtime (e.g., C may be logspace, nondeterministic logspace, NCkor Alogtime itself). With our alternating logtime algorithm for tree canonization,one can immediately give a recursive enumeration of all intrinsic tree predicateswhich are computable in C . Namely, one enumerates the C -algorithms whichfirst create a canonical representation of their input tree and then operateonly on the canonical representation. It is clear that every algorithm of thistype computes a property of trees which is independent of the representationof the tree, and conversely, every C -algorithm which computes a property oftrees independent of their representations is equivalent to an algorithm in thisenumeration.In the next section we give technical definitions regarding trees, includingthe definition of the linear ordering of trees and the string representation oftrees. Section 3 is devoted to the alternating logarithmic time algorithm fortree isomorphism. Then, in sections 4 and 5, we present the algorithms for treecomparison and tree canonization.It is easy to check that our results apply also to labeled trees, with onlyrelatively minor changes to the definitions and algorithms.2 Technical Definitions for TreesThe parent of a node x in a tree T is the unique node adjacent to x whichis closer to the root. The children of a node x are the nodes of which x is2the parent. A node without any children is a leaf.Anodexis an ancestor ofanodey if the shortest path from y to the root contains x; in this case wealso say y is a descendent of x.Ifxis a node of T , there is a subtree of Trooted at x, namely the node x plus all of its descendents. (Some authorsuse the terminology “maximal subtree”, but for this paper, a subtree is alwaysmaximal.) An immediate subtree of T is a subtree whose root is a child of T ’sroot node. If S is a proper subtree of T , then the parent tree of S is the subtreeof T of which S is an immediate subtree.A second, more formal, inductive definition of tree isomorphism or treeequality, ≡, is given next. The size of T , denoted |T |, equals the number ofleaf nodes in T .Definition (Tree equality). Let S and T be trees. We define S ≡ T by inductionon the number of nodes in S and T by defining that S ≡ T holds if and only if(a) |S| = |T | =1 or(b) S and T both have the same number, m, of immediate