On the Smallest Synchronizing Terms of Finite Tree Automata

This paper deals with properties of synchronizing terms for finite tree automata, which is a generalization of the synchronization principle of deterministic finite string automata (DFA). Such terms correspond to a connected subgraph, where a state in the root is always the same regardless of states of subtrees attached to it. We ask, what is the maximum height of the smallest synchronizing term of a deterministic bottom-up tree automaton (DFTA) with [Formula: see text] states. This naturally leads to two types of synchronizing terms, called weak and strong, that depend on whether a variable, i.e., a placeholder for a subtree, must be present in at least one leaf or all of them. We prove that the maximum height in the case of weak synchronization has a theoretical upper bound [Formula: see text], where [Formula: see text] is the maximum length of the shortest synchronizing string of an [Formula: see text]-state DFAs. For strong synchronization, we prove exponential bounds. We provide a theoretical upper bound of [Formula: see text] for the height and two constructions of automata approaching it. One achieves the height of [Formula: see text] with an alphabet of linear size and maximum arity [Formula: see text], and the other achieves [Formula: see text] with an alphabet of quadratic size.