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
A Taxonomy of Minimisation Algorithms for Deterministic Tree Automata
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. Stellenbosch University, ZA-7602 Matieland, South Africa.
2016 (engelsk)Inngår i: Journal of universal computer science (Online), ISSN 0948-695X, E-ISSN 0948-6968, Vol. 22, nr 2, s. 180-196Artikkel i tidsskrift (Fagfellevurdert) Published
Resurstyp
Text
Abstract [en]

We present a taxonomy of algorithms for minimising deterministic bottom-up tree automata (DTAs) over ranked and ordered trees. Automata of this type and its extensions are used in many application areas, including natural language processing (NLP) and code generation. In practice, DTAs can grow very large, but minimisation keeps things manageable. The proposed taxonomy serves as a unifying framework that makes algorithms accessible and comparable, and as a foundation for efficient implementation. Taxonomies of this type are also convenient for correctness and complexity analysis, as results can frequently be propagated through the hierarchy. The taxonomy described herein covers a broad spectrum of algorithms, ranging from novel to well-studied ones, with a focus on computational complexity.

sted, utgiver, år, opplag, sider
2016. Vol. 22, nr 2, s. 180-196
Emneord [en]
deterministic bottom-up tree automata, automata minimisation, algorithm taxonomies
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-122590ISI: 000376442200002OAI: oai:DiVA.org:umu-122590DiVA, id: diva2:939683
Tilgjengelig fra: 2016-06-20 Laget: 2016-06-20 Sist oppdatert: 2018-06-07bibliografisk kontrollert

Open Access i DiVA

fulltext(233 kB)58 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 233 kBChecksum SHA-512
88aa19cafe84202fe418679c37abba58eeb5a7ad079b412afa7d400b9d83988f389c29ed55a4b64dd4d2e043f78ce35bd3a2835d0209bdbd3ec0c7d693ab0ad8
Type fulltextMimetype application/pdf

Personposter BETA

Björklund, JohannaCleophas, Loek

Søk i DiVA

Av forfatter/redaktør
Björklund, JohannaCleophas, Loek
Av organisasjonen
I samme tidsskrift
Journal of universal computer science (Online)

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 58 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 372 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