Definability of Tree Transformations

点击翻译按钮获取中文摘要

This project is concerned with expanding the theory of tree transformations by solving severaldifficult long-standing open questions. These questions are concerned with "definability", i.e.,given a large class of transformation, we wish to decide, whether a given transformationof the large class, can also be realized by a transducer from a smaller class. Often the smaller class is obtained by restricting the resources of the larger class; for instance, we may want to know if a given translation can be realized by a class that is streamable with constant memory. The three definability problems that we wish to address are natural and open problems within the theory of tree transformations:1. Is it decidable for a given functional bottom-up tree transducer whether or not its translation can be defined by a (deterministic) top-down tree transducer?2. Is it decidable for a given attributed tree transducer (with look-ahead) whether or not its translation can be defined by a top-down tree transducer?3. Is a (total deterministic) macro tree translation definable by an attributed transducer if and only if the number of distinct output subtrees is linearly bounded by the size of each input tree?We claim that due to new results on string and tree transducers, we are now in a positionto give solutions to these open problem.