On the smallest synchronizing terms of finite tree automata

Štěpán Plachý, 3 Apr 2023

Finite automata are extensively studied for various properties. One such property are synchronizing words, i.e., words that reach the same state regardless of what state we start in. One studied question in this field in this field is, what is the worst case length of the shortest synchronizing word for an n-state automaton. So far it is known that the worst case is polynomial and is bounded by \((n-1)^2\) and \((n^3-n)/6\) and the lower bound is conjectured to be tight. A tree automaton is an extension of finite automata for tree structures (or terms). We study the synchronization property of this extended formalism. We identify two types of synchronizing terms - weak and strong, and further study the bounds for the worst case height of the smallest synchronizing term of respective type for an n-state tree automaton. We show that for terms of maximal arity (number of children) 1 the worst case for height is identical to the worst case length in string automata, for weakly synchronizing term it is asymptotically upper bounded by the worst case length in string automata (which is polynomial), and for strongly synchronizing terms we show the worst case is bounded by exponentials depending on maximal arity and size of the alphabet in the automaton.