umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Inngår i: Implementation and Application of Automata : 11th International Conference, CIAA 2006, 2006, s. 699-713Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
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
Tilgjengelig fra: 2009-06-02 Laget: 2009-06-02 Sist oppdatert: 2018-06-08

Open Access i DiVA

Fulltekst mangler i DiVA

Personposter BETA

Högberg, Johanna

Søk i DiVA

Av forfatter/redaktør
Högberg, Johanna
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 707 treff
RefereraExporteraLink to record
Permanent link

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