umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture notes in computer science, ISSN 0302-9743
Identifiers
URN: urn:nbn:se:umu:diva-23165OAI: oai:DiVA.org:umu-23165DiVA: 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

urn-nbn

Altmetric score

urn-nbn
Total: 144 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf