The Universality of Higher-Order Attributed Tree Transducers

In this paper we present higher-order attributed tree transducers as a formal computational model for higher-order attribute grammars. The latter is a generalization of the classical concept of attribute grammars in the sense that during attribute evaluation, the input tree can be enlarged by inserting subtrees which were computed during attribute evaluation. We prove the universality of this formalism by showing that the class of functions described by higher-order attributed tree transducers coincides with the class of (partial) recursive tree functions. Received May 12, 1999. Online publication December 5, 2000.