Tree automata and separable sets of input variables


Sl. Shtrakov, Vl. Shtrakov




We introduce the separable sets of variables for trees and tree automata. If a set $Y$ of input variables is inseparable for a tree and an automaton, then there a non empty family of distributive sets of $Y$ . It is shown that if a tree t has ``many'' inseparable sets with respect to a tree automaton $\mathcal A$, then there is an effective way to reduce the complexity of $\mathcal A$ when running on $t$.