Top-down tree transducers with regular look-ahead. (English) Zbl 0369.68048

Math. Syst. Theory 10(1976), 289-303 (1977); erratum in Theory Comput. Syst. 58, No. 2, 377-379 (2016).


68Q45 Formal languages and automata
Full Text: DOI


[1] A. Arnold andM. Dauchet, Transductions de forets regulieres monadiques; forets coregulieres,RAIRO 10 (1976), 5–28.
[2] P. R. J. Asveld, Controlled iteration grammars and full hyper-AFL’s,Memoradum 114, Technical University Twente, Holland, 1976.
[3] B. S. Baker, Tree transductions and families of tree languages, Ph.D. Thesis, Harvard University,Report TR-9-73, 1973 (also:5th Theory of Computing, 200–206). · Zbl 0319.68040
[4] K. Čulik II andR. Cohen, LR-regular grammars–an extension of LR(k) grammars,JCSS 7 (1973), 66–96. · Zbl 0253.68014
[5] P. J. Downey, Tree transducers andETOL tree systems (abstract),Conference on Formal Languages, Automata and Development, Noordwijkerhout, Holland, 1975.
[6] A. Ehrenfeucht andG. Rozenberg, On inverse homomorphic images of deterministicETOL languages,LOCOS 13, Utrecht University, Holland, 1974.
[7] J. Engelfriet, Bottom-up and top-down tree transformations–a comparison,Math. Syst. Theory 9 (1975), 198–231. This paper is also referred to as BT. · Zbl 0335.68061
[8] J. Engelfriet, Surface tree languages and parallel derivation trees,DAIMI Report PB-44, Aarhus University, Denmark, 1975 (to appear in Theoretical Computer Science).
[9] G. T. Herman andG. Rozenberg,Developmental systems and languages, North-Holland Publ. Co., Amsterdam, 1975. · Zbl 0306.68045
[10] J. E. Hopcroft andJ. D. Ullman,Formal languages and their relation to automata, Addison-Wesley Publ. Co., Reading, Mass., 1969. · Zbl 0196.01701
[11] L. S. Levy andA. K. Joshi, Some results in tree automata,Math. Syst. Theory 6 (1973), 334–342. · Zbl 0249.68028
[12] W. F. Ogden andW. C. Rounds, Composition ofn transducers,4th Symp. on Theory of Computing, 1972, pp. 198–206. · Zbl 0358.68089
[13] W. C. Rounds, Mappings and grammars on trees,Math. Syst. Theory,4 (1970), 257–287. · Zbl 0203.30103
[14] J. W. Thatcher, Generalized2 sequential machine maps,JCSS 4 (1970), 339–367. · Zbl 0198.03303
[15] J. W. Thatcher, Tree automata: an informal survey, in:Currents in the Theory of Computing (ed. A. V. Aho), Prentice-Hall, 1973, pp. 143–172.
[16] M. Dauchet,Transductions inversibles de forets, These, Univ. de Lille, France, 1975.
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.