This paper continues a long series by the first author, alone and with others, beginning in 1975, all devoted to tree transformations--their properties and applications, especially in models for syntax-directed semantics as used by a preprocessor. The reader is “assumed to be familiar” with macro tree transducers, attribute grammars, monadic second-order logic (MSO), and MSO translations. The authors direct the reader to a recent monograph surveying macro (MTT) and attributed (ATT) tree transducers for the necessary background information [1].
After this warning, a “Preliminaries” section begins with definitions for the set of natural numbers and the empty set. This material varies widely, from the overly simple to that desperately needing a simple explanatory example. The paper works better, however, as a report of new research results.
First, every MSO-definable tree translation can be realized by an MTT. This result is achieved through the close relationship between single use restricted (sur) ATTs and MTTs with lookahead. The sur property applies to the unshared use of attributes. A partial converse holds as well for single use restricted MTTs with regular lookahead, where a corresponding MSO transducer can be constructed. Proving that an MSO tree translation can be found for every MTT is listed as future work.
Second, the sur is very restrictive, so that the first result holds for relatively few MTTs. It is, however, extended to MTTs with finite copying, where each parameter, or formalization of an attribute, may be copied a bounded number of times. This easing of sur expands the class of MTTs for which MSO transducers can be obtained.