Change search
ReferencesLink to record
Permanent link

Direct link
Bisimulation minimization of tree automata
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2006 (English)In: Implementation and Application of Automata : 11th International Conference, CIAA 2006, 2006, 699-713 p.Conference paper (Refereed)
Abstract [en]

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
URN: urn:nbn:se:umu:diva-23165OAI: diva2:220744
Available from: 2009-06-02 Created: 2009-06-02 Last updated: 2009-10-23

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Högberg, Johanna
By organisation
Department of Computing Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 102 hits
ReferencesLink to record
Permanent link

Direct link