Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
Brenda S. Baker · SIAM Journal on Computing · 1978
When trees are denoted by “terms” or “parenthesized expressions”, which are strings, the class of top-down tree transducers (automata which map trees into trees and read their input trees from the root toward the leaves) form a subclass of a nondeterministic version of the generalized syntax directed translations of Aho and Ullman. It is shown that every nondeterministic syntax directed translation (NGSDT), and therefore every top-down tree transduction, can be carried out by a Turing machine which uses an amount of work space which is linear with respect to the size of the input and output. For every n, the family consisting of the images of recognizable sets of trees under the composition of n top-down transductions is shown to be properly contained in the family of deterministic context-sensitive languages.