A pumping lemma for output languages of macro tree transducers

The concept of macro tree transducer is a formal model for studying properties of syntax-directed translations and of functional languages which are based on primitive recursion. In this paper, for output languages of producing and nondeleting macro tree transducers, we introduce and prove a pumping lemma. We apply this pumping lemma to gain two results: (1) there is no producing and nondeleting macro tree transducer which computes the set of all monadic trees with double exponential height as output and (2) there are hierarchies of producing and nondeleting macro tree transducers with respect to their number of functions. (orig.)Available from FIZ Karlsruhe / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman