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
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 (Engelska)Ingår i: Journal of universal computer science (Online), ISSN 0948-695X, E-ISSN 0948-6968, Vol. 22, nr 2, s. 180-196Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2016. Vol. 22, nr 2, s. 180-196
Nyckelord [en]
deterministic bottom-up tree automata, automata minimisation, algorithm taxonomies
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:umu:diva-122590ISI: 000376442200002OAI: oai:DiVA.org:umu-122590DiVA, id: diva2:939683
Tillgänglig från: 2016-06-20 Skapad: 2016-06-20 Senast uppdaterad: 2018-06-07Bibliografiskt granskad

Open Access i DiVA

fulltext(233 kB)58 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 233 kBChecksumma SHA-512
88aa19cafe84202fe418679c37abba58eeb5a7ad079b412afa7d400b9d83988f389c29ed55a4b64dd4d2e043f78ce35bd3a2835d0209bdbd3ec0c7d693ab0ad8
Typ fulltextMimetyp application/pdf

Personposter BETA

Björklund, JohannaCleophas, Loek

Sök vidare i DiVA

Av författaren/redaktören
Björklund, JohannaCleophas, Loek
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
Journal of universal computer science (Online)
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 58 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

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