A taxonomy of minimisation algorithms for deterministic tree automata

J. Bjorklund, L. Cleophas

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Citaties (Scopus)

Uittreksel

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.

TaalEngels
Pagina's180-196
TijdschriftJournal of Universal Computer Science
Volume22
Nummer van het tijdschrift2
StatusGepubliceerd - 2016
Extern gepubliceerdJa

Trefwoorden

    Citeer dit

    @article{691c413f8ffa4184abdcc16398cbb25c,
    title = "A taxonomy of minimisation algorithms for deterministic tree automata",
    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.",
    keywords = "deterministic bottom-up tree automata, automata minimisation, algorithm taxonomies",
    author = "J. Bjorklund and L. Cleophas",
    year = "2016",
    language = "English",
    volume = "22",
    pages = "180--196",
    journal = "Journal of Universal Computer Science",
    issn = "0948-6912",
    publisher = "Springer",
    number = "2",

    }

    A taxonomy of minimisation algorithms for deterministic tree automata. / Bjorklund, J.; Cleophas, L.

    In: Journal of Universal Computer Science, Vol. 22, Nr. 2, 2016, blz. 180-196.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    TY - JOUR

    T1 - A taxonomy of minimisation algorithms for deterministic tree automata

    AU - Bjorklund,J.

    AU - Cleophas,L.

    PY - 2016

    Y1 - 2016

    N2 - 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.

    AB - 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.

    KW - deterministic bottom-up tree automata

    KW - automata minimisation

    KW - algorithm taxonomies

    M3 - Article

    VL - 22

    SP - 180

    EP - 196

    JO - Journal of Universal Computer Science

    T2 - Journal of Universal Computer Science

    JF - Journal of Universal Computer Science

    SN - 0948-6912

    IS - 2

    ER -