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.