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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B. S. Baker, Tree transductions and families of tree languages,Ph.D.Thesis, Harvard University, 1973, andProc. 5th Ann. ACM Symp. on Theory of Computing (1973), 200–206.
J. Doner, Tree acceptors and some of their applications,J. Comp. Syst. Sci. 4 (1970), 406–451.
S. Ginsburg,The mathematical theory of context-free languages, McGraw-Hill Book Co., New York, 1966.
J. E. Hopcroft andJ. D. Ullman,Formal languages and their relation to automata, Addison-Wesley Publ. Co., Reading, Mass., 1969.
M. Magidor andG. Moran, Finite automata over finite trees, Hebrew University,Technical Report No. 30, 1969.
W. C. Rounds, Trees, transducers and transformations,Ph. D. Thesis, Stanford University, 1968.
W. C. Rounds, Map**s and grammars on trees,Math. Systems Theory 4 (1970), 257–287.
J. W. Thatcher, Generalized2 sequential machine maps,IBM Res. Report RC 2466, 1969.
J. W. Thatcher, Generalized2 sequential machine maps,J. Comp. Syst. Sci. 4 (1970), 339–367.
J. W. Thatcher, There's a lot more to finite automata theory than you would have thought,Proc. 4th Ann. Princeton Conf. on Informations Sciences and Systems (1970), 263–276. Also published in revised form under the title “Tree automata: an informal survey” inCurrents in the Theory of Computing (ed. A. V. Aho), Prentice-Hall, 1973, 143–172.
J. W. Thatcher andJ. B. Wright, Generalized finite automata theory with an application to a decision-problem of second-order logic,Math. Systems Theory 2 (1968), 57–81.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Engelfriet, J. Bottom-up and top-down tree transformations— a comparison. Math. Systems Theory 9, 198–231 (1975). https://doi.org/10.1007/BF01704020
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01704020