Helmut Seidl. Deciding Equivalence of Finite Tree Automata. In Burkhard Monien and Robert Cori, editors, Theoretical Aspects of Computer Science, volume 349 of Lecture Notes in Computer Science, pages 480-492, Paderborn, Germany, February 1989. Springer.

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.

Reference: Bibtex The original publication is available at www.springerlink.com