Tree transducers

Haruo HosoyaCambridge 2010 · DOI · OpenAlex

Abstract

Tree transducers form a class of finite-state models that not only accept trees but also transform them. While in Chapter 7 we described a simple yet very powerful tree transformation language, μXDuce, tree transducers are more restricted and work with only a finite number of states. An important aspect of the restriction is that tree transducers can never use intermediate data structure. However, this restriction is not too unrealistic, as it is one of the design principles of the XSLT language – currently the most popular language for XML transformation. In addition, this restriction leads to several nice properties that otherwise would hardly hold; among the most important is the exact typechecking property to be detailed in Chapter 11. The present chapter introduces two standard tree transducer frameworks, namely, top-down tree transducers and macro tree transducers, and shows their basic properties.
BibTeX
@inproceedings{hosoya2010tree,
  author = {Haruo Hosoya},
  title = {{Tree transducers}},
  booktitle = {Cambridge},
  year = {2010},
  doi = {10.1017/cbo9780511762093.011},
}

Loading related content...

Figure