Static Garbage Collection

We present a method that allows to bound the sizes of intermediate trees in a composition of macro tree transducers. Macro tree transducers are a powerful model of tree translation which, for instance, includes all attribute grammars (seen as tree-to-tree translators). The idea of the method is to change a transducer in the composition so that it does not produce output nodes that will be removed (and ignored) by a subsequent transducer in the composition. This can be considered as a form of static garbage collection, where garbage is never produced by any transducer. We then give three applications of this result and show that (1) compositions of macro tree transducers can be computed in linear time with respect to the sum of sizes of input and output trees, (2) finiteness of ranges of compositions of macro tree transducers is decidable, and (3) the macro tree transducer composition hierarchy collapses when restricted to functions of linear size increase.