  Straight-line (linear) context-free tree (SLT) grammars have been used to
compactly represent ordered trees. It is well known that equivalence of SLT
grammars is decidable in polynomial time. Here we extend this result and show
that isomorphism of unordered trees given as SLT grammars is decidable in
polynomial time. The proof constructs a compressed version of the canonical
form of the tree represented by the input SLT grammar. The result is
generalized to unrooted trees by "re-rooting" the compressed trees in
polynomial time. We further show that bisimulation equivalence of unrooted
unordered trees represented by SLT grammars is decidable in polynomial time.
For non-linear SLT grammars which can have double-exponential compression
ratios, we prove that unordered isomorphism is PSPACE-hard and in EXPTIME. The
same complexity bounds are shown for bisimulation equivalence.
