Storage-to-tree transducers with look-ahead

We generalize Engelfriet's decomposition result stating that the class of transformations induced by top-down tree transducers with regular look-ahead is equal to the composition of the class of top-down tree transformations and the class of linear tree homomorphisms. Replacing the input trees with an arbitrary storage type, the top-down tree transducers are turned into regular storage-to-tree transducers. We show that the class of transformations induced by regular storage-to-tree transducers with positive look-ahead is equal to the composition of the class of transformations induced by regular storage-to-tree transducers with the class of linear tree homomorphisms. We also show that the classes of transformations induced by both IO and OI context-free storage-to-tree transducers are closed under positive look-ahead, and are closed under composition with linear tree homomorphisms. (C) 2004 Elsevier B.V. All rights reserved.