Pushdown machines for the macro tree transducer (Q1089810)

The goal of this paper is to find machines which characterize the class of translations induced by macro tree transducers. Roughly speaking, a macro tree transducer can be considered as a machine taking trees as (input) configurations where the label of the root of a tree can be tested and subtrees can be selected (storage type TR). The control of the macro tree transducer consists of a system of recursive function procedures in which calls may occur nestedly and in parallel (control or program type CFT). The general concept of separating program and storage type of a machine proves to be fruitful and it is adhered to throughout. Along with that the idea of storage type simulation is elaborated. The main topic of this paper is to implement the nested recursion inherent in macro tree transducers on pushdown machines, i.e., on machines with a simpler control but a more complicated storage. In a short formula the main results in the total deterministic case are \(D_ tCFT(TR)=D_ tRT(P(TR))\) where the control type RT means recursive function procedures without context parameters, and its analogue for macro tree-to-string transducers. Moreover, characterizations of n-fold compositions of macro tree (-to-string) transducers are established. The proof provides characterizations of CFT(S) and MAC(S) where S is an arbitrary storage type, and it follows the general idea \(''macro=indexed=nested\) stack'': Rather than transforming the known proofs for grammars (S trivial) into proofs for tree transducers uniform proofs for X(S)-transducers are given specializing to both the grammar case and the tree transducer case \((S=TR)\). Indeed, in that way several known results are obtained as corollaries: attribute grammars can be simulated by total deterministic macro tree transducers [\textit{P. Franchi- Zannettacci}, 1982]; the classes of OI context-free languages and of languages accepted by restricted pushdown tree automata coincide [\textit{I. Guessarian}, Math. Syst. Theory 16, No.4, 237-263 (1983; Zbl 0524.68047)]; OI macro grammars and indexed grammars are equivalent [\textit{M. J. Fischer}, 1968]; the tree-walking pushdown transducer of \textit{T. Kamimura} [Inf. Control 57, 1-20 (1983; Zbl 0549.68080)] is a special case of the \(D_ tREG(P^ 2(TR))\)-transducer; indexed grammars are equivalent to indexed pushdown automata [\textit{R. Parchmann}, \textit{J. Duske} and \textit{J. Specht}, Inf. Control 45, 48-67 (1980; Zbl 0438.68035)]. In order to make the proofs of the general results of this paper rigorous, some of the definitions and lemmata tend to be a bit complex so that at one place the authors recommend explicitly to the reader ''to let himself be guided by the easy intuition behind the concept of simulation'' and possibly, on first reading, to skip a few technical details.