Composition of restricted Macro Tree Transducers
| Author: | J. Voigtländer |
|---|---|
| Published: | Master thesis, Technische Universität Dresden, defended in April 2001. |
| BibTeX: | Voi01.bib |
| Abstract: | A special class of functional programs can be modelled by Macro Tree Transducers. We present a technique that can be used to solve the efficiency problems due to creation and consumption of intermediate results in such functional programs, by constructing for two given Macro Tree Transducers, with appropriate restrictions, a single Macro Tree Transducer that implements the composition of the two original ones. We show that this is possible, if the first Macro Tree Transducer is non-copying and the second one is weakly single-use. Thus, we obtain the characterization MAC_nc;MAC_wsu=MAC, which generalizes a previous result. We also develop two post-processing constructions that can be used for optimizing the Macro Tree Transducer obtained from the composition construction, by eliminating superfluous context parameters and superfluous traversals through the input tree. Further, we present two interesting applications of the above characterization to problems about non-copying Macro Tree Transducers. |
| Download: | CompositionOfRestrictedMacroTreeTransducers.ps.gz |
An article based on this thesis appeared in Journal of Functional Programming, see here.