Helmut Seidl. Deciding Equivalence of Finite Tree Automata. SIAM J. Comput., 19(3):424-437, 1990.
We show: for every constant m it can be decided in polynomial time whether or not two m-ambiguous finite tree automata are equivalent. In general, inequivalence for finite tree automata is DEXPTIME-complete w.r.t. logspace reductions, and PSPACE-complete w.r.t. logspace reductions, if the automata in question are supposed to accept only finite languages. For finite tree automata with coefficients in a field R we give a polynomial time algorithm for deciding ambiguity-equivalence provided R-operations and R-tests for 0 can be performed in constant time. We apply this algorithm for deciding ambiguity-inequivalence of finite tree automata in randomized polynomial time. Furthermore, for every constant m we show that it can be decided in polynomial time whether or not a given finite tree automaton is m-ambiguous.