  The computational complexity of the isomorphism problem for regular trees,
regular linear orders, and regular words is analyzed. A tree is regular if it
is isomorphic to the prefix order on a regular language. In case regular
languages are represented by NFAs (DFAs), the isomorphism problem for regular
trees turns out to be EXPTIME-complete (resp. P-complete). In case the input
automata are acyclic NFAs (acyclic DFAs), the corresponding trees are
(succinctly represented) finite trees, and the isomorphism problem turns out to
be PSPACE-complete (resp. P-complete). A linear order is regular if it is
isomorphic to the lexicographic order on a regular language. A polynomial time
algorithm for the isomorphism problem for regular linear orders (and even
regular words, which generalize the latter) given by DFAs is presented. This
solves an open problem by Esik and Bloom.
