Macro tree transducers (Q1073576)

Tree transducers are mathematical tools which transform trees into trees. There exist two main categories of such systems: bottom-up (frontier-to- root) tree transducers which process the tree from leaves towards root and top-down (root-to-frontier) tree transducers which work in the opposite direction. Macro tree transducers are a generalization of the top-down tree transducers by considering states of any rank and rules of the form \(q(\sigma (x_ 1,...,x_ m),y_ 1,...,y_ n)\Rightarrow t\) where \(q\in Q\) is a state of rank \(n+1\), \(\sigma\) is a symbol of rank m from the input alphabet \(\Sigma\), \(x_ 1,...,x_ m\) are input variables, \(y_ 1,...,y_ n\) are (formal) parameters and t is a tree over Q and the output alphabet \(\Delta\) of special form. The derivation process is defined in usual way and, similar to context-free tree grammars, we have two restricted derivations: inside-out (IO) derivations and outside-in (IO) derivations. As a practical application, macro tree transducers serve as model for the concept of syntax-directed semantics ''with context''. This paper gives formal definition for macro tree transducers and investigates the properties of induced transformation classes. The connection with context-free tree grammars is studied and the extension with regular look-ahead is considered. The last section contains conclusions and gives valuable ideas for future work.