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

Joost Engelfriet

    Research output: Contribution to journalArticleAcademic

    233 Citations (Scopus)
    237 Downloads (Pure)


    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
    Issue number2
    Publication statusPublished - 1975


    • IR-85444

    Cite this