Definability of Tree Transformations

这个项目关注的是通过解决几个长期存在的难题来扩展树变换理论。这些问题涉及“可定义性”，即，给定一个大类变换，我们希望决定，是否一个给定的大类变换也可以由一个较小类的变换器来实现。通常，较小的类是通过限制较大类的资源来获得的;例如，我们可能想知道给定的翻译是否可以通过一个具有常量内存的可流式传输的类来实现。我们希望解决的三个可定义性问题是树变换理论中的自然和开放问题：1。对于一个给定的功能自下而上的树型转换器，它的转换是否可以由一个（确定性的）自上而下的树型转换器来定义，这是可判定的吗？2.对于一个给定的属性树转换器（具有前瞻性），其转换是否可以由自顶向下的树转换器定义，这是可判定的吗？3.当且仅当不同的输出子树的数量由每个输入树的大小线性限制时，一个（完全确定的）宏树转换可由属性转换器定义吗？我们声称，由于弦和树传感器的新结果，我们现在能够给出这些开放问题的解决方案。

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.