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
A Taxonomy of Minimisation Algorithms for Deterministic Tree Automata
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Umeå University, Faculty of Science and Technology, Department of Computing Science. Stellenbosch University, ZA-7602 Matieland, South Africa.
2016 (English)In: Journal of universal computer science (Online), ISSN 0948-695X, E-ISSN 0948-6968, Vol. 22, no 2, 180-196 p.Article in journal (Refereed) Published
Resource type
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.

Place, publisher, year, edition, pages
2016. Vol. 22, no 2, 180-196 p.
Keyword [en]
deterministic bottom-up tree automata, automata minimisation, algorithm taxonomies
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:umu:diva-122590ISI: 000376442200002OAI: oai:DiVA.org:umu-122590DiVA: diva2:939683
Available from: 2016-06-20 Created: 2016-06-20 Last updated: 2017-11-28Bibliographically approved

Open Access in DiVA

fulltext(233 kB)36 downloads
File information
File name FULLTEXT01.pdfFile size 233 kBChecksum SHA-512
88aa19cafe84202fe418679c37abba58eeb5a7ad079b412afa7d400b9d83988f389c29ed55a4b64dd4d2e043f78ce35bd3a2835d0209bdbd3ec0c7d693ab0ad8
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Björklund, JohannaCleophas, Loek
By organisation
Department of Computing Science
In the same journal
Journal of universal computer science (Online)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 36 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 57 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