Bottom-up and top-down tree transformation - a comparison. (English) Zbl 0335.68061


68Q45 Formal languages and automata
68N01 General topics in the theory of software
05C05 Trees
Full Text: DOI


[1] 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. · Zbl 0319.68040
[2] J. Doner, Tree acceptors and some of their applications,J. Comp. Syst. Sci. 4 (1970), 406–451. · Zbl 0212.02901
[3] S. Ginsburg,The mathematical theory of context-free languages, McGraw-Hill Book Co., New York, 1966. · Zbl 0184.28401
[4] J. E. Hopcroft andJ. D. Ullman,Formal languages and their relation to automata, Addison-Wesley Publ. Co., Reading, Mass., 1969. · Zbl 0196.01701
[5] M. Magidor andG. Moran, Finite automata over finite trees, Hebrew University,Technical Report No. 30, 1969.
[6] W. C. Rounds, Trees, transducers and transformations,Ph. D. Thesis, Stanford University, 1968.
[7] W. C. Rounds, Mappings and grammars on trees,Math. Systems Theory 4 (1970), 257–287. · Zbl 0203.30103
[8] J. W. Thatcher, Generalized2 sequential machine maps,IBM Res. Report RC 2466, 1969.
[9] J. W. Thatcher, Generalized2 sequential machine maps,J. Comp. Syst. Sci. 4 (1970), 339–367. · Zbl 0198.03303
[10] 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.
[11] 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. · Zbl 0196.01901
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.