Tree transducers with external functions (Q1208712)

Macro tree transducers, which formalize the idea of syntax-directed translation, and attributed tree transducers, which provide a semantic model for attribute grammars, are known to be closely related. Both of these transducer types are enhanced with the possibility of invoking external functions. The intuitive idea suggested by the authors is that the use of external functions formalizes the concept of modularity. The main result shows that any tree function computable by a macro tree transducer with external functions from a given class \({\mathcal U}\) can be represented as the composition of a simple auxiliary function, a tree homomorphism and a tree function computed by a one-visit attributed tree transducer with external functions from \({\mathcal U}\). The class PREC of primitive recursive tree functions can be defined as the smallest class of tree functions which contains certain base functions and is closed under composition and primitive recursion. Macro tree transducers with external functions define an operator on the class of all tree functions which maps any class \({\mathcal U}\) of tree functions to the class \(\text{MT}(U)\) of functions computed by macro tree transducers with external functions from \(U\). Similarly, attributed tree transducers with external functions define an operator on the class of all tree functions. The second main result shows that the class PREC remains unchanged if the scheme of primitive recursion is replaced by either one of these operators.