Bisimulation minimization of tree automata
2006 (English)In: Implementation and Application of Automata : 11th International Conference, CIAA 2006, 2006, 699-713 p.Conference paper (Refereed)
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 O ((r) over cap log n), where (r) over cap 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.
Place, publisher, year, edition, pages
2006. 699-713 p.
, Lecture notes in computer science, ISSN 0302-9743
IdentifiersURN: urn:nbn:se:umu:diva-23165OAI: oai:DiVA.org:umu-23165DiVA: diva2:220744