A taxonomy of minimisation algorithms for deterministic tree automata
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
J.UCS Consortium
Abstract
We 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.
Description
CITATION: 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.
The original publication is available at http://www.jucs.org
The original publication is available at http://www.jucs.org
Keywords
Algorithms, Computer science -- Mathematics, Machine theory
Citation
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.