Seminar Formal Grammars WS 06/07

Abstract. The concept of top-down tree transducers is known since decades and the purpose of this paper is to give a smooth introduction into this concept. Within this context, we consider the notion of copying, a copying normal form and a corresponding algorithm. This leads to the presentation of the intercalation lemma that is used to establish a language hierarchy on a special class of tree transducers with respect to the copying-bound parameter.