On the finite degree of ambiguity of finite tree automata (Q1825038)

The tree automata considered here are nondeterministic root-to-frontier (or top-down) tree recognizers. The degree of ambiguity of such an automaton is defined as the maximum of the number of different accepting computations for any input tree. The author proves that it can be decided in polynomial time (in terms of the number of states) whether the degree of ambiguity of a given tree automaton is finite or infinite. Moreover, he gives an upper bound for finite degrees of ambiguity as a function of the number of states and the greatest rank of a symbol in the alphabet. The bound is essentially optimal.