It is well-known that the shortest synchronizing words for any automata lies between $n^2$ and roughly $n^3$. We focused on the same question but for tree automata, i.e., what are the “smallest” terms which sychronize a tree automaton?

It became clear that classical notion of sychronization does not 1-to-1 correspond to this new setting, so we define “weak” and “strong” synchronization and show bounds for both. The weak sychronization is more string-like – the interesting part of simpmlest synchronization terms boil down to a single path which is basically a string. Surprisingly, the classical lower-bounds for strings stop working in this setting as it is not at all obvious that the sychronizing term cannot do something clever with the two subtrees to sychronize swiftly – this takes mental effort to persuade yourself that is it not trivial.

For string sychronization all leaves ought to be variables so no trivializing substitution as in the weak case can take place. Here, height of the smallest sychronizing term seems to be dependant on size of the alphabet. We show how to reduce binary subtractor with $n$ bits using $2n$ states and a linear alphabet. Also, we reduce iteration through combinations on $n$ bits using $n+\sqrt{n}$ states and quadratic alphabet. While upper bounds is known to be exponential (the same one from strings works) these lower bounds show that we are far from the string case.