A taxonomy of minimisation algorithms for deterministic tree automata

Simple item page
dc.contributor.authorBjorklund, Johannaen_ZA
dc.contributor.authorCleophas, Loeken_ZA
dc.date.accessioned2017-07-13T12:14:03Z
dc.date.available2017-07-13T12:14:03Z
dc.date.issued2016
dc.descriptionCITATION: Bjorklund, J. & Cleophas, L. 2016. A taxonomy of minimisation algorithms for deterministic tree automata. Journal of Universal Computer Science, 22(2):180-196, doi:10.3217/jucs-022-02-0180.
dc.descriptionThe original publication is available at http://www.jucs.org
dc.description.abstractWe present a taxonomy of algorithms for minimising deterministic bottomup 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.en_ZA
dc.description.urihttp://www.jucs.org/jucs_22_2/a_taxonomy_of_minimisation
dc.description.versionPublisher's version
dc.format.extent17 pages
dc.identifier.citationBjorklund, J. & Cleophas, L. 2016. A taxonomy of minimisation algorithms for deterministic tree automata. Journal of Universal Computer Science, 22(2):180-196, doi:10.3217/jucs-022-02-0180.
dc.identifier.issn0948-6968 (online)
dc.identifier.otherdoi:10.3217/jucs-022-02-0180
dc.identifier.urihttp://hdl.handle.net/10019.1/101968
dc.language.isoen_ZAen_ZA
dc.publisherJ.UCS Consortium
dc.rights.holderJournal of Universal Computer Science
dc.subjectAlgorithmsen_ZA
dc.subjectComputer science -- Mathematicsen_ZA
dc.subjectMachine theoryen_ZA
dc.titleA taxonomy of minimisation algorithms for deterministic tree automataen_ZA
dc.typeArticleen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
bjorklund_taxonomy_2016.pdf
Size:
155.36 KB
Format:
Adobe Portable Document Format
Description:
Download article
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.95 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Research Articles (Information Science)