BISIMULATION MINIMIZATION OF TREE AUTOMATA
Parosh Aziz Abdulla, Johanna Högberg, Lisa Kaati · International Journal of Foundations of Computer Science · 2007
We extend an algorithm by Paige and Tarjan that solves the coarsest stable refinement problem to the domain of trees. The algorithm is used to minimize nondeterministic tree automata (NTA) with respect to bisimulation. We show that our algorithm has an overall complexity of [Formula: see text], where [Formula: see text] is the maximum rank of any symbol in the input alphabet, m is the total size of the transition table, and n is the number of states.