Project Details
Projekt Print View

Definability of Tree Transformations

Subject Area Theoretical Computer Science
Term since 2020
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 441896869
 
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.
DFG Programme Research Grants
International Connection Belgium, France, Netherlands
 
 

Additional Information

Textvergrößerung und Kontrastanpassung