Domains of Partial Attributed Tree Transducers

The domains of partial attributed tree transducers (patt's) are the tree languages recognized by tree walking automata in universal acceptance mode. Moreover, the domains of patt's having monadic output are the tree languages recognized by deterministic tree walking automata. Key words: Formal Languages; Attribute Grammars; Tree Automata 1 Introduction An attribute grammar (ag) [Knu68] can be seen as a device that translates derivation trees of a context-free grammar G 0 into expressions over some signature. Abstracting from G 0 we obtain an attributed tree transducer (att) [Ful81]. An att A is a total deterministic device that translates all trees in T \Sigma (the set of trees over a ranked alphabet \Sigma) into output trees in T \Delta . If we allow A to be a partial att (patt), then the domain of A is a tree language L over \Sigma, i.e., a subset of T \Sigma . Now the question arises, which tree languages L can be the domain of patt's (equivalently: partial ag's)? From [Bar81..