Indexed languages are a classical notion in formal language theory. As the language
equivalent of second-order pushdown automata, they have received considerable attention …

We consider injective first-order interpretations that input and output trees of bounded
height. The corresponding functions have polynomial output size, since a first-order …

Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and
P. Černý in 2010 as a one-way deterministic automata model to define transductions of finite …

This is a book on weighted tree automata. We present the basic definitions and some of the
important results in a coherent form with full proofs. The concept of weighted tree automata …

This Hilbert Method, as discussed in this paper, is the idea to encode combinatorial objects
used by automata, such as words or trees, into algebraic objects, such as numbers and …

We study the class of rational recursive sequences (ratrec) over the rational numbers. A
ratrec sequence is defined via a system of sequences using mutually recursive equations of …

Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and
P. Černý in 2010 as a one-way deterministic automata model to define transductions of finite …

The decidability of equivalence for three important classes of tree transducers is discussed.
Each class can be obtained as a natural restriction of deterministic macro tree transducers …

In the past decades, classical results from algebra, including Hilbert's Basis Theorem, had
various applications in formal languages, including a proof of the Ehrenfeucht Conjecture …

A tree transducer with origin translates an input tree into a pair of output tree and origin
information. The origin information maps each node in the output tree to the unique node in …