High level tree transducers and iterated pushdown tree transducers (Q1096399)

n-level tree transducers (n\(\geq 0)\) combine the features of n-level tree grammars and of top-down tree transducers in the sense that the derivations of the tree grammars are syntax-directed by input trees. For running n, the sequence of n-level tree transducers starts with top-down tree transducers \((n=0)\) and macro tree transducers \((n=1)\). In this paper the class of tree-to-tree translations computed by n-level tree transducers is characterized by n-iterated pushdown tree transducers. Such a transducer can be considered as a regular tree grammar of which the derivations are syntax-directed by n-iterated pushdown of trees; an n-iterated pushdown of trees is a pushdown of pushdowns of... of pushdowns (n times) of trees. In particular, we investigate the total deterministic case, which is relevant for syntax-directed semantics of programming languages.