The study of graph structure has advanced in recent years with great strides: finite graphs
can be described algebraically, enabling them to be constructed out of more basic elements …

The theory of tree automata and tree languages emerged in the middle of the 1960s quite
naturally from the view of finite automata as unary algebras advocated by JR Biichi and JB …

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 …

A characterization is given of the class of tree translations definable in monadic second-
order logic (MSO), in terms of macro tree transducers. The first main result is that the MSO …

Extended top-down tree transducers (transducteurs généralisés descendants; see [A. Arnold
and M. Dauchet, Bi-transductions de forêts, in Proceedings of the 3rd International …

Two well-known formalisms for the specification and computation of tree transductions are
compared: the mso graph transducer and the attributed tree transducer with look-ahead …

The first main result is that if a macro tree translation is of linear size increase, ie, if the size
of every output tree is linearly bounded by the size of the corresponding input tree, then the …

The n-pebble tree transducer was recently proposed as a model for XML query languages.
The four main results on deterministic transducers are: First,(1) the translation τ of an n …

With attribute coupled grammars, descriptions of subsequent compilation phases can be
composed to a single phase on the description level. This creates the opportunity for …

Context-free S grammars are introduced, for arbitrary (storage) type S, as a uniform
framework for recursion-based grammars, automata, and transducers, viewed as programs …