umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Bisimulation minimization of tree automata
Umeå universitet, Teknisk-naturvetenskaplig fakultet, Institutionen för datavetenskap.
2006 (Engelska)Ingår i: Implementation and Application of Automata : 11th International Conference, CIAA 2006, 2006, s. 699-713Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
2006. s. 699-713
Serie
Lecture notes in computer science, ISSN 0302-9743
Identifikatorer
URN: urn:nbn:se:umu:diva-23165OAI: oai:DiVA.org:umu-23165DiVA, id: diva2:220744
Tillgänglig från: 2009-06-02 Skapad: 2009-06-02 Senast uppdaterad: 2018-06-08

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Högberg, Johanna

Sök vidare i DiVA

Av författaren/redaktören
Högberg, Johanna
Av organisationen
Institutionen för datavetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 655 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf