Intercalation lemmas for tree transducer languages

摘要

We develop intercalation lemmas for the computations of the top-down tree transducers defined by Rounds and Thatcher. These lemmas are used to prove necessary conditions for languages, all of whose strings are of exponential length, to be tree transducer languages. The language {ww: w∈{a, b}*, |w|=2n, n≥0}, which is generable by the composition of two transducers, is shown not to be generable by one. The proof technique applies to bottom-up transducers as well. The results are related to some subclasses of Woods' Augmented Transition Networks characterized elsewhere in terms of tree transducer languages.