Bottom-up and top-down tree transformations - a comparison

Joost Engelfriet

    Research output: Contribution to journalArticleAcademic

    219 Citations (Scopus)
    64 Downloads (Pure)

    Abstract

    The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations. A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.
    Original languageUndefined
    Pages (from-to)198-231
    JournalMathematical systems theory
    Volume9
    Issue number2
    DOIs
    Publication statusPublished - 1975

    Keywords

    • IR-85444

    Cite this

    Engelfriet, Joost. / Bottom-up and top-down tree transformations - a comparison. In: Mathematical systems theory. 1975 ; Vol. 9, No. 2. pp. 198-231.
    @article{3b52146546ff419ba164031e2bf1d392,
    title = "Bottom-up and top-down tree transformations - a comparison",
    abstract = "The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations. A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.",
    keywords = "IR-85444",
    author = "Joost Engelfriet",
    year = "1975",
    doi = "10.1007/BF01704020",
    language = "Undefined",
    volume = "9",
    pages = "198--231",
    journal = "Theory of computing systems",
    issn = "1432-4350",
    publisher = "Springer",
    number = "2",

    }

    Bottom-up and top-down tree transformations - a comparison. / Engelfriet, Joost.

    In: Mathematical systems theory, Vol. 9, No. 2, 1975, p. 198-231.

    Research output: Contribution to journalArticleAcademic

    TY - JOUR

    T1 - Bottom-up and top-down tree transformations - a comparison

    AU - Engelfriet, Joost

    PY - 1975

    Y1 - 1975

    N2 - The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations. A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.

    AB - The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations. A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.

    KW - IR-85444

    U2 - 10.1007/BF01704020

    DO - 10.1007/BF01704020

    M3 - Article

    VL - 9

    SP - 198

    EP - 231

    JO - Theory of computing systems

    JF - Theory of computing systems

    SN - 1432-4350

    IS - 2

    ER -