  Given two messages - as linear sequences of letters, it is immediate to
determine whether one can be transformed into the other by simple substitution
cipher of the letters. On the other hand, if the letters are carried as labels
on nodes of topologically isomorphic unordered trees, determining if a
substitution exists is referred to as marked tree isomorphism problem in the
literature and has been show to be as hard as graph isomorphism. While the
left-to-right direction provides the cipher of letters in the case of linear
messages, if the messages are carried by unordered trees, the cipher is given
by a tree isomorphism. The number of isomorphisms between two trees is roughly
exponential in the size of the trees, which makes the problem of finding a
cipher difficult by exhaustive search. This paper presents a method that aims
to break the combinatorics of the isomorphisms search space. We show that in a
linear time (in the size of the trees), we reduce the cardinality of this space
by an exponential factor on average.
