Composition closure of linear extended top-down tree transducers (Q519891)

The extended top-down tree transducers studied in this paper differ from the standard model in that they may process in one step a larger fragment of an input tree than just a single symbol. This generalization has been found useful especially in applications to syntax-directed machine translation. The transducers considered here are linear, i.e., no rule creates multiple copies of a subtree of an input tree, and they are presented as synchronous grammars that generate in parallel an input tree and an output tree. An extension l-XT\(^{\mathrm R}\) of the class l-XT of the tree transformations defined by linear extended top-down tree transducers is obtained by allowing a form of regular look-ahead. Several subclasses of these two basic classes are obtained by imposing upon the transducers some combination of the restrictions of \(\varepsilon\)-freeness, strictness and nondeletion. For any class \(\mathcal{C}\) of tree transformations that includes all identity transformations, the classes \(\mathcal{C}^n\) of relational compositions of \(n\) members of \(\mathcal{C}\) (\(n\geq 1\)) form an ascending hierarchy \(\mathcal{C} \subseteq \mathcal{C}^2 \subseteq \mathcal{C}^3 \subseteq \ldots\). Since complex tree transformations may be defined as compositions of simpler ones, it is desirable that the class \(\mathcal{C}\) of tree transformations used is closed under composition, i.e., that \(\mathcal{C}^2 \subseteq \mathcal{C}\), or at least that \(\mathcal{C}^{n+1} = \mathcal{C}^n\) for some small value of \(n\). For some of the classes indicated above, the composition hierarchy was already known, and in this paper the authors settle the remaining cases. It turns out that none of the classes is closed under composition, but that most of the classes of \(\varepsilon\)-free transducers yield finite hierarchies. The authors determine the lengths of the finite hierarchies, and they also exhibit many relationships between the different hierarchies.