The subject of this book is the investigation of tree transducers. Tree
trans- ducers were introduced in theoretical computer science in order
to study the general properties of formal models which give semantics to
context-free languages in a syntax-directed way. Such formal models
include attribute grammars with synthesized attributes only,
denotational semantics, and at- tribute grammars (with synthesized and
inherited attributes). However, these formal models share certain
constituents which are irrelevant in the investi- gation of the general
properties considered in this book. In particular, we can abstract (a)
from derivation trees of the context-free grammar and take trees over
some ranked alphabet, (b) from the semantic domain of the model and use
the initial term algebra instead, and finally (c) from the machine-
oriented computation paradigm, which maintains the incarnation
information of recursive function calls, and take a term rewriting
semantics instead. Ap- plying these three abstraction steps to attribute
grammars with synthesized attributes only, to denotational semantics,
and to attribute grammars we obtain the concepts of top-down tree
transducer, macro tree transducer, and attributed tree transducer,
respectively. The macro attributed tree transducer combines the concepts
of the macro tree transducer and the attributed tree transducer. This
book explores the general properties of these four types of tree
transducers.