Aurélie Lagoutte
email: aurelie.lagoutte@ens-cachan.fr

Andreas Maletti
email: andreas.maletti@ims.uni-stuttgart.de

Survey: Weighted Extended Top-down Tree Transducers Part III -Composition

Keywords: weighted tree transducer, top-down tree transducer, composition, deletion, copying

In this survey (functional) compositions of weighted tree transformations computable by weighted extended top-down tree transducers are investigated. The existing results in the literature are explained and illustrated. It is argued, why certain compositions are not possible in the general case, and 3 informed conjectures provide an insight into potentially 3 new composition results that extend and complement the existing results. In particular, if all were true, then the beautiful symmetry in the composition results for weighted top-down and bottom-up tree transducers would be recovered.

Motivation

Weighted tree transducers [START_REF] Kuich | Tree transducers and formal tree series[END_REF][START_REF] Engelfriet | Bottom-up and top-down tree series transformations[END_REF][START_REF] Fülöp | Tree series transformations that respect copying[END_REF] (also called 'tree series transducers') are a joint generalization of the unweighted tree transducer (such as the top-down tree transducer [START_REF] Rounds | Mappings and grammars on trees[END_REF][START_REF] Thatcher | Generalized 2 sequential machine maps[END_REF] or the bottom-up tree transducer [START_REF] Thatcher | Tree automata: An informal survey[END_REF]) and the weighted tree automaton [START_REF] Berstel | Recognizable formal power series on trees[END_REF][START_REF] Bozapalidis | The rank of a formal tree power series[END_REF][START_REF] Alexandrakis | Weighted grammars and Kleene's theorem[END_REF][START_REF] Kuich | Formal power series over trees[END_REF][START_REF] Ésik | Formal tree series[END_REF][START_REF] Borchardt | Determinization of finite state weighted tree automata[END_REF][START_REF] Borchardt | The Theory of Recognizable Tree Series[END_REF]. A good overview over both predecessors is presented in [START_REF] Fülöp | Weighted tree automata and tree transducers[END_REF]. For a more detailed historic account and an in-depth introduction into weighted extended top-down tree transducers, we refer the reader to the first part [START_REF] Maletti | Survey: Weighted extended top-down tree transducers -Part I: Basics and expressive power[END_REF] of this survey. A popular application area that has driven tree transducer research in the past few years is (syntax-based) machine translation [START_REF] Koehn | Statistical phrase-based translation[END_REF][START_REF] Koehn | Statistical Machine Translation[END_REF]. The second part [START_REF] Maletti | Survey: Weighted extended top-down tree transducers -Part II: Application in machine translation[END_REF] of this survey attempts to present a high-level perspective on some of the essential problems and algorithms used in this application domain.

The work was carried out while the first author was an intern at Universität Stuttgart. Financially supported by the German Research Foundation (DFG) grant MA/4959/1-1.

In this part of the survey, we will investigate compositions of weighted extended (top-down) tree transducers. Such a tree transducer computes a weighted relation between input and output trees (i.e., it assigns a weight to each pair of input and output trees). Two such relations can be composed in the usual manner with the only difference that a weight (for example, a confidence or a probability) is returned each time "membership is tested". Using the real numbers as weight structure, we compose two weighted relations τ 1 : A × B → IR and τ 2 : B × C → IR by requiring that

(τ 1 ; τ 2 )(a, c) = b∈B τ 1 (a, b) • τ 2 (b, c) (1)
for all a ∈ A and c ∈ C. For the sake of simplicity, let us assume that B is finite. Equation ( 1) can be imagined in an operational manner. The first process transforms the input a into an intermediate product b at a certain cost τ 1 (a, b). This intermediate product is then fed into the second process, which transforms it into a final product at cost τ 2 (b, c). Thus, the components are executed in a sequential manner. Traditionally, the multiplicative operation of the weight structure (typically, a semiring [START_REF] Hebisch | Semirings -Algebraic Theory and Applications in Computer Science[END_REF][START_REF] Golan | Semirings and their Applications[END_REF]) is used to combine weights of processes that are executed in series (or in sequence). Consequently, we multiply the weights τ 1 (a, b) • τ 2 (b, c) to obtain the cost of producing c from a via the intermediate product b. Naturally, there might be a choice of intermediate products that are all suitable to some degree to produce the output c. Thus, we sum over all the possibilities of producing c from a.

Compositions have been and are used in a number of application areas as diverse as machine translation [START_REF] Yamada | A decoder for syntax-based statistical MT[END_REF] and functional program optimization [START_REF] Kühnemann | Benefits of tree transducers for optimizing functional programs[END_REF]. The complexity of a given tree transformation problem can be tackled and broken down into smaller pieces with the help of (de-)composition in a divide-andconquer approach. Once all the subproblems have been solved, the individual solutions can be recombined with the help of composition. This approach is used in [START_REF] Yamada | A decoder for syntax-based statistical MT[END_REF], where a translation model is broken into 3 smaller pieces:

a reordering component, which changes the order of subtrees but keeps the trees otherwise intact, an insertion component, which has the ability to spontaneously add subtrees to the output of the translation, and a translation component, which just translates the words (or phrases) occuring in the input tree.

These components can now be trained and optimized individually (even from different resources). However, since the evaluation of composition chains can be very inefficient [START_REF] May | Efficient inference through cascades of weighted tree transducers[END_REF], automatic procedures that "compose" finite representations of such weighted relations are desirable. Naturally, the obtained finite representation should compute the composition of the weighted relations computed by the input representations. As expected, the finite representation discussed in this survey is the weighted extended top-down tree transducer (xtt) together with its variants.

In contrast to the first part [START_REF] Maletti | Survey: Weighted extended top-down tree transducers -Part I: Basics and expressive power[END_REF] of this survey, we do not require a complete semiring [START_REF] Hebisch | Semirings -Algebraic Theory and Applications in Computer Science[END_REF][START_REF] Golan | Semirings and their Applications[END_REF] here, which yields that we have to avoid infinite summations. This change prompts a minor change in the definition of the model because we have to disallow rules that contain no input and output symbol at all. In fact, infinite sums also restrict the potential compositions because we have to guarantee that the sum in [START_REF] Alexandrakis | Weighted grammars and Kleene's theorem[END_REF] is finite. This is achieved by two simple conditions, of which each is sufficient to guarantee the finiteness of the sum in [START_REF] Alexandrakis | Weighted grammars and Kleene's theorem[END_REF]. Moreover, we introduce a simple variant of our main model that has rule identifiers in order to simplify the composition constructions. The additional indirection via identifiers allows us to construct the same rule several times under different names. In this way we can obtain a closer and more direct relationship between the rules of the input xtt and the composed xtt.

In the main part of this survey, we investigate compositions of xtt. In other words, given two xtt M and N , we want to construct another xtt that computes the composition of the weighted tree transformations computed by the xtt M and N . It is known that already in the unweighted setting, this cannot always be achieved, and we will consider two important cases:

compositions of an xtt with a top-down tree transducer, and compositions of selected xtt with top-down tree transducers that can additionally have ε-rules.

The former case has been investigated in the unweighted case by [START_REF] Engelfriet | Bottom-up and top-down tree transformations: A comparison[END_REF][START_REF] Baker | Composition of top-down and bottom-up tree transductions[END_REF] and these results were partially lifted to the weighted setting in [START_REF] Engelfriet | Bottom-up and top-down tree series transformations[END_REF][START_REF] Maletti | Compositions of tree series transformations[END_REF][START_REF] Maletti | The Power of Tree Series Transducers[END_REF]. We recall all the relevant results and complement them by three conjectured results that handle the missing cases. More precisely, we conjecture:

that a constant xtt can be composed with a linear top-down tree transducer (see Conjecture 11), where the property 'constant' will be introduced here, that a deterministic xtt can be composed with a nondeleting top-down tree transducer (see Conjecture 13), and that a constant and deterministic xtt can be composed with any top-down tree transducer (see Conjecture 14).

We explain why these conjectured cases cause additional problems, which are due to the presence of weights. While we will not present a formal construction for each case, we present a generic composition construction and then indicate how to modify it to obtain a formal construction for the individual cases. The latter case, in which we compose an xtt with a top-down tree transducer with ε-rules, was investigated in [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF] in the unweighted setting. Here, we extend the results of [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF] to the weighted setting and conjecture a new result (see Conjecture 23), which is again based on the new property 'constant'. Overall, our conjectured results complement the existing results nicely, and if all were true, then we would obtain the beautiful symmetry in the weighted setting that is known from compositions [START_REF] Engelfriet | Bottom-up and top-down tree transformations: A comparison[END_REF][START_REF] Baker | Composition of top-down and bottom-up tree transductions[END_REF] for unweighted top-down and bottom-up tree transducers [START_REF] Thatcher | Tree automata: An informal survey[END_REF].

Notation

The set of all nonnegative integers is IN, and we let

[n] = {i ∈ IN | 1 ≤ i ≤ n} for every n ∈ IN. We fix the set X = {x i | i ∈ IN} of (formal) variables.
The set of all finite words (or sequences) over a set S is S * , where ε is the empty word. The concatenation of the words v, w ∈ S * is v.w or simply vw. The length of a word w ∈ S * is denoted by |w|. An alphabet Σ is a nonempty and finite set, of which the elements are called symbols. For every alphabet Q, we let 3 with leaf labels S is the smallest set U such that S ⊆ U and σ(u 1 , . . . , u k ) ∈ U for every k ∈ IN, σ ∈ Σ, and u 1 , . . . , u k ∈ U . We often omit qualifications like 'for all k ∈ IN' if it is obvious from the context that k is a nonnegative integer. Moreover, we generally assume that Σ ∩ S = ∅, and thus we write σ() simply as σ for every σ ∈ Σ. Given another alphabet ∆, we treat elements of T ∆ (T Σ (S)) and Q(T Σ (S)) as particular trees of T Q∪Σ∪∆ (S). 4 Finally, we write T Σ for T Σ (∅).

Q(S) = {q(s) | q ∈ Q, s ∈ S}. The set T Σ (S) of Σ-trees
Next, we define a few operations on trees. The set pos(t) ⊆ IN * of positions of a tree t ∈ T Σ (S) is inductively defined by pos(s) = {ε} for every s ∈ S and

pos(σ(t 1 , . . . , t k )) = {ε} ∪ {i.w | i ∈ [k], w ∈ pos(t i )}
for every σ ∈ Σ and t 1 , . . . , t k ∈ T Σ (S). The set pos(t) of positions is (totally) ordered by the lexicographic order on IN * . Let t, t ∈ T Σ (S) and w ∈ pos(t). The label of t at position w is t(w), and the w-rooted subtree of t is t| w . Formally, these notions can be defined by s(ε) = s| ε = s for every s ∈ S and

σ(t 1 , . . . , t k )(ε) = σ σ(t 1 , . . . , t k )(i.v) = t i (v) σ(t 1 , . . . , t k )| ε = σ(t 1 , . . . , t k ) σ(t 1 , . . . , t k )| i.v = t i | v for every σ ∈ Σ, t 1 , . . . , t k ∈ T Σ (S), i ∈ [k]
, and v ∈ pos(t i ). For every subset L ⊆ Σ ∪ S of labels and s ∈ S, we let pos L (t) = {w ∈ pos(t) | t(w) ∈ L} and pos s (t) = pos {s} (t). The expression t[u] w denotes the tree that is obtained from t ∈ T Σ (S) by replacing the subtree t| w at position w by u ∈ T ∆ (S).

The following operations implicitly always use the fixed set X of variables. We let var(t) = {x ∈ X | pos x (t) = ∅}. The tree t is linear if every x ∈ X occurs at most once in t. A substitution θ : X → T Σ (S) can be applied to a tree t ∈ T Σ (S), and returns the tree tθ that is obtained by replacing (in parallel) all occurrences of each variable x ∈ X by θ(x). Formally, (i) xθ = θ(x) for every x ∈ X, (ii) sθ = s for every s ∈ S \ X, and (iii) σ(t 1 , . . . , t k )θ = σ(t 1 θ, . . . , t k θ) for every σ ∈ Σ and t 1 , . . . , t k ∈ T Σ (S).

A (commutative) semiring [START_REF] Hebisch | Semirings -Algebraic Theory and Applications in Computer Science[END_REF][START_REF] Golan | Semirings and their Applications[END_REF] is an algebraic structure (A, +, •, 0, 1) consisting of two commutative monoids (A, +, 0) and (A, •, 1) such that • distributes over finite sums (including the empty sum, which yields a • 0 = 0 for all a ∈ A). The semiring A is idempotent if 1 + 1 = 1. 5 Examples of semirings include the Boolean semiring ({0, 1}, max, min, 0, 1), which is idempotent, the powerset6 semiring (P(S), ∪, ∩, ∅, S) for some set S, which is idempotent, the tropical semiring (IR ∪ {∞}, min, +, ∞, 0), which is also idempotent, the nonnegative integers (IN, +, •, 0, 1), and the semiring of real numbers (IR, +, •, 0, 1).

Let S and T be sets, and let (A, +, •, 0, 1) be a semiring. A weighted relation r from S to T is a mapping r : S ×T → A. Moreover, for every mapping f : S → A, we let supp(f ) = {s ∈ S | f (s) = 0}. Thus, supp(r) ⊆ S × T .

From now on, let (A, +, •, 0, 1) be an arbitrary semiring such that 0 = 1.

Next, let us recall the weighted extended (top-down) tree transducer [START_REF] Dauchet | Transductions inversibles de forêts. Thèse 3ème cycle[END_REF][START_REF] Arnold | Bi-transductions de forêts[END_REF][START_REF] Knight | An overview of probabilistic tree transducers for natural language processing[END_REF][START_REF] Graehl | Training tree transducers[END_REF]. We essentially follow the definitions of [START_REF] Maletti | Compositions of extended top-down tree transducers[END_REF][START_REF] Maletti | The power of extended top-down tree transducers[END_REF], in which the corresponding unweighted device is discussed in detail. An in-depth presentation of the weighted device can be found in the first part [START_REF] Maletti | Survey: Weighted extended top-down tree transducers -Part I: Basics and expressive power[END_REF] of this survey. A (weighted) extended (top-down) tree transducer (xtt) is a tuple (Q, Σ, ∆, I, R), where -Q is a finite set of states, -Σ and ∆ are alphabets of input and output symbols such that

Q∩(Σ∪∆) = ∅, -I ⊆ Q is a set of initial states, and -R : Q(T Σ (X)) × T ∆ (Q(X)) → A assigns rule weights such that supp(R) is
finite and for every (l, r) ∈ supp(R) we have that {l, r} ⊆ Q(X), l is linear, and var(r) ⊆ var(l). 7For the following discussion, let M = (Q, Σ, ∆, I, R) be an xtt. The elements of supp(R) are called rules (of M ), and we often write them as l → r instead of (l, r). We call l and r of a rule l → r the left-and right-hand side, respectively. Moreover, we write l → r ∈ R instead of (l, r) ∈ supp(R), and we write l

a → r ∈ R instead of R(l, r) = a. A rule l → r ∈ R is (i) linear if r is linear, (ii) nondeleting if var(r) = var(l), and (iii) simple if |pos Σ (l)| = 1. In addition, the rule l → r is -consuming if |pos Σ (l)| ≥ 1,
and an ε-rule otherwise, and producing if |pos ∆ (r)| ≥ 1, and erasing otherwise. 8The xtt M is (i) linear, (ii) nondeleting, and (iii) a top-down tree transducer [START_REF] Kuich | Tree transducers and formal tree series[END_REF][START_REF] Engelfriet | Bottom-up and top-down tree series transformations[END_REF] (tdtt) if every rule l → r ∈ R is (i) linear, (ii) nondeleting, and (iii) simple, respectively. Moreover, the xtt M is Boolean if R(l, r) = 1 for every l → r ∈ R.

The semantics of the xtt M is given by term rewriting [START_REF] Engelfriet | Top-down tree transducers with regular look-ahead[END_REF][START_REF] Baader | Term Rewriting and All That[END_REF][START_REF] Maletti | The power of extended top-down tree transducers[END_REF]. To simplify our composition constructions later on, we immediately present a semantics that can handle "foreign" symbols, which are symbols that are not in Q ∪ Σ ∪ ∆. 9 Let Σ and ∆ be such that Σ ⊆ Σ and ∆ ⊆ ∆ . The elements of T ∆ (Q(T Σ (X))) are called sentential forms. A position w ∈ pos Q (ξ) in a sentential form ξ is reducible (for M ) if there exists a rule l → r ∈ R and a substitution θ : X → T Σ (X) such that ξ| w = lθ. Let ξ, ζ ∈ T ∆ (Q(T Σ (X))) be sentential forms and l → r ∈ R be a rule. We say that ξ rewrites to ζ using l → r, denoted by ξ ⇒ (l,r) M ζ, if there exists a substitution θ : X → T Σ (X) such that ξ| w = lθ and ζ = ξ[rθ] w where w is the least reducible position in pos Q (ξ) with respect to the lexicographic total ordering on IN * . 10 As usual, we use ';' for relation composition, thus for example,

(⇒ ρ1 M ; ⇒ ρ2 M ) = {(ξ, ζ) | ∃ξ : ξ ⇒ ρ1 M ξ ⇒ ρ2 M ζ} .
The (extended) weighted relation τ M (or weighted tree transformation) computed by M is given by 11 Finally, the xtt M is deterministic 12 (respectively, total ) if for all q ∈ Q and t ∈ T Σ there exists at most (respectively, at least) one u ∈ T ∆ such that (q(t), u) ∈ supp(τ M ). 13

τ M (ξ, ζ) = ρ1,...,ρ k ∈supp(R) ξ⇒ ρ 1 M ;•••;⇒ ρ k M ζ k i=1 R(ρ i ) for every ξ, ζ ∈ T ∆ (Q(T Σ (X))). The semantics τ M of the xtt M is the weighted relation τ M : T Σ × T ∆ → A such that τ M (t, u) = q∈I τ M (q(t), u) for every t ∈ T Σ and u ∈ T ∆ .

An Example Composition

We start our investigation into compositions of xtt with an example to illustrate the problem and the general principle used to solve it. Roughly speaking, given two xtt M and N we want to construct a single xtt that behaves like the two xtt M and N in sequence. Before we move to the formal definition of composition, let us introduce two example xtt and demonstrate derivations (i.e., term rewrite steps). 9 A definition of the semantics without this extension can be found in [START_REF] Maletti | Survey: Weighted extended top-down tree transducers -Part I: Basics and expressive power[END_REF]. 10 Given a sentential form ξ and a rule ρ ∈ R, there exists at most one sentential form ζ such that ξ ⇒ ρ M ζ. 11 Since the xtt M cannot consume symbols from Σ \ Σ and cannot produce symbols from ∆ \∆, the semantics τM does not depend on the particular choice of Σ and ∆ . 12 This property should correctly be called 'unambiguous', but for historical reasons we use 'deterministic' in the following. 13 For top-down tree transducers these properties are typically defined using syntactic restrictions [START_REF] Engelfriet | Bottom-up and top-down tree transformations: A comparison[END_REF][START_REF] Baker | Composition of top-down and bottom-up tree transductions[END_REF], which imply our corresponding semantic conditions. It requires a significant technical overhead to generalize the syntactic conditions faithfully to xtt, so we chose to present only the semantic property. Example 1. We assume that the used semiring is the semiring (IR, +, •, 0, 1) of real numbers. Let M = ({q 0 , q 1 }, Σ, Γ, {q 0 }, R) be the xtt with input alphabet Σ = {σ, α}, output alphabet Γ = {f, h, b}, and the following rules:

q 0 σ σ x 1 x 2 α 2 → f q 1 x 1 q 0 x 2 q 0 σ α x 1 3 → q 0 x 1 q 0 α 1 → b q 1 x 1 2 → h q 0 x 1 q 1 x 1 5 → h q 1 x 1
ρ 1 : q 0 (σ(σ(x 1 , x 2 ), α)) 2 -→ f (q 1 (x 1 ), q 0 (x 2 )) ρ 4 : q 1 (x 1 ) 2 -→ h(q 0 (x 1 ))
ρ 2 : q 0 (σ(α, x 1 ))

3

-→ q 0 (x 1 ) ρ 5 : q 1 (x 1 )

5

-→ h(q 1 (x 1 ))

ρ 3 : q 0 (α) 1 -→ b .
We illustrate these rules in Fig. 1

, ρ 5 ρ 1 -ρ 3 ρ 2 ρ 1 , ρ 3 -ρ 5 ρ 1 -ρ 5 ρ 1 -ρ 5
Next, let us demonstrate a derivation using M . As input and output tree we consider s = σ(σ(α, σ(α, σ(α, α))), α)

and t = f (h(h(b)), b) .
Figure 2 shows a derivation from q 0 (s) to t. Its weight is

R(ρ 1 ) • R(ρ 5 ) • R(ρ 4 ) • R(ρ 3 ) • R(ρ 2 ) • R(ρ 2 ) • R(ρ 3 ) = 2 • 5 • 2 • 1 • 3 • 3 • 1 = 180
It is easy to verify that this is the only possible derivation from q 0 (s) to t. Since q 0 is the only initial state, we can conclude that τ M (s, t) = 180.

Example 2. We keep the semiring of real numbers as our used semiring. A second xtt is given by N = ({p}, Γ, ∆, {p}, R ), where Γ = {f, h, b}, ∆ = {λ, γ, δ, β}, and R contains the rules:

µ 1 : p(x 1 ) 2 -→ γ(p(x 1 )) µ 4 : p(h(x 1 )) 8 -→ δ(p(x 1 )) µ 2 : p(f (x 1 , x 2 )) 5 -→ λ(p(x 1 ), p(x 2 )) µ 5 : p(b) 1 -→ β µ 3 : p(f (x 1 , x 2 )) 5 -→ λ(β, λ(p(x 1 ), p(x 2 ))) .
Again, the properties of the rules are documented in the following table. We observe that the xtt N is linear and nondeleting.

q 0 σ σ α σ α σ α α α ⇒ ρ1 M f q 1 α q 0 σ α σ α α ⇒ ρ5 M f h q 1 α q 0 σ α σ α α ⇒ ρ4 M f h h q 0 α q 0 σ α σ α α ⇒ ρ3 M f h h b q 0 σ α σ α α ⇒ ρ2 M f h h b q 0 σ α α ⇒ ρ2 M f h h b q 0 α ⇒ ρ3 M f h h b b Fig. 2. A derivation from q0(s) to t in M (see Example 1). ε-rule consuming erasing producing linear nondeleting µ 1 µ 2 -µ 5 µ 1 -µ 5 µ 1 -µ 5 µ 1 -µ 5
This time we illustrate a derivation for the input and output tree

t = f (h(h(b)), b) and u = λ(β, λ(δ(δ(β)), β)) .
Figure 3 shows the unique derivation from p(t) to u. It has the weight Composition is the process of running two xtt one after the other. In this way, the output tree of the first xtt becomes the input tree of the second xtt.

R (µ 3 ) • R (µ 4 ) • R (µ 4 ) • R (µ 5 ) • R (µ 5 ) = 5 • 8 • 8 • 1 • 1 = 320 .
For example, the output tree t generated by the xtt M in Example 1 can be processed by the xtt N of Example 2, which is demonstrated in Example 2. Thus, in a composition of M and N (see Examples 1 and 2) we can transform the input tree s of Example 1 immediately to the output tree u of Example 2 by first running the xtt M on s to produce the intermediate tree t, which can then be transformed into u by N .

Formally, two weighted tree relations (of suitable type) are composed as follows. Let τ 1 :

T Σ × T Γ → A and τ 2 : T Γ × T ∆ → A be weighted relations. Their composition (τ 1 ; τ 2 ) : T Σ × T ∆ → A is the weighted relation such that (τ 1 ; τ 2 )(s, u) = t∈T Γ τ 1 (s, t) • τ 2 (t, u) (2)
for every s ∈ T Σ and u ∈ T ∆ . Clearly, this definition generalizes the classical definition of composition for relations. Whereas the infinite sum is not a problem in the unweighted case (where it is an infinite disjunction that becomes true once one element is true), we have to address it in the weighted case. There are essentially two options:

(i) to permit infinite sums and require that the semiring is suitably rich to handle infinite sums [START_REF] Hebisch | Semirings -Algebraic Theory and Applications in Computer Science[END_REF][START_REF] Golan | Semirings and their Applications[END_REF], which was done in [START_REF] Engelfriet | Bottom-up and top-down tree series transformations[END_REF][START_REF] Fülöp | Hierarchies of tree series transformations. Theoret[END_REF][START_REF] Fülöp | Tree series transformations that respect copying[END_REF][START_REF] Maletti | Compositions of tree series transformations[END_REF][START_REF] Maletti | The Power of Tree Series Transducers[END_REF][START_REF] Fülöp | Weighted tree automata and tree transducers[END_REF] and also in the first part [START_REF] Maletti | Survey: Weighted extended top-down tree transducers -Part I: Basics and expressive power[END_REF] of this survey, or (ii) to avoid the infinite sums by restricting the weighted relations (and thus the xtt) that we allow in compositions.

In this part, we will follow the second approach by requiring that in a composition τ 1 ; τ 2 we have that

{t | (s, t) ∈ supp(τ 1 )} or {t | (t, u) ∈ supp(τ 2 )} (3)
is finite for every s ∈ T Σ and u ∈ T ∆ . It is clear that in both cases the sum (2) in the definition of the composition τ 1 ; τ 2 is finite. Let us illustrate the general approach that is used in most composition constructions. To construct an xtt that computes the composition τ M ; τ N of the weighted relations computed by two xtt M and N , we need to make sure that the intermediate tree t (in Examples 1 and 2) is never constructed explicitly. To achieve this, the second xtt has to immediately consume every intermediate symbol that is produced by the first xtt M . Let us illustrate this approach by combining the two derivations of Figs. 2 and3 such that intermediate symbols (from Γ ) are consumed as soon as possible. The obtained derivation that now uses rules of both M and N is displayed in Fig. 4.

Once we have reordered the rule applications as indicated in the previous paragraph, we "glue" all rule applications that produce intermediate symbols together with the rule applications that consume these symbols. In this step, we also interpret two adjacent states (one of M and one of N ) as in p(q(s)) as a single state p, q . For example, based on Fig. 4 we glue the first two rule applications (of the rules ρ 1 and µ 3 ) together to obtain a single rule application of the rule p, q 0 (σ(σ(x 1 , x 2 ), α))

p q 0 σ σ α σ α σ α α α ⇒ ρ1 M p f q 1 α q 0 σ α σ α α ⇒ µ3 N λ β λ p q 1 α p q 0 σ α σ α α ⇒ ρ5 M λ β λ p h q 1 α p q 0 σ α σ α α ⇒ µ4 N λ β λ δ p q 1 α p q 0 σ α σ α α ⇒ ρ4 M λ β λ δ p h q 0 α p q 0 σ α σ α α ⇒ µ4 N λ β λ δ δ p q 0 α p q 0 σ α σ α α ⇒ ρ3 M λ β λ δ δ p b p q 0 σ α σ α α ⇒ µ5 N λ β λ δ δ β p q 0 σ α σ α α ⇒ ρ2 M λ β λ δ δ β p q 0 σ α α ⇒ ρ2 M λ β λ δ δ β p q 0 α ⇒ ρ3 M λ β λ δ δ β p b ⇒ µ5 N λ β λ δ δ β β
2•5 --→ λ(β, λ( p, q 1 (x 1 ), p, q 0 (x 2 ))) ,
which is displayed in Fig. 5. For the rest of the discussion, we drop the distinction between rule applications and rules. In general, several rules of the first xtt need to be "glued" with several rules of the second xtt. However, it was already shown in [START_REF] Arnold | Morphismes et bimorphismes d'arbres[END_REF] (and in the second part [START_REF] Maletti | Survey: Weighted extended top-down tree transducers -Part II: Application in machine translation[END_REF] of this survey) that this strategy does not work in general (even if both xtt M and N are linear and nondeleting). In the rest of this survey, we will thus focus on simpler cases, in which the left-hand sides of the rules of the second xtt N contain at most one input symbol. In Sect. 5 we consider compositions of an xtt M with a top-down tree transducer N . Thus, in Sect. 5 the second xtt N is such that every rule has exactly one input symbol in its left-hand side. We relax this requirement slightly in Sect. 6, where we investigate compositions of an xtt M with a top-down tree transducer N with ε-rules [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF], which is an xtt in which each rule contains at most one input symbol in its left-hand side. However, before we proceed with the mentioned composition constructions we first introduce a modification of our xtt model that will prove to be useful in Sections 5 and 6.

p, q 0 σ σ x 1 x 2 α 2•5 -→ λ β λ p, q 1 x 1 p, q 0 x 2

An Equivalent Model

In this section, we introduce an alternative description for weighted extended top-down tree transducers that will be useful for our composition constructions. Essentially, we introduce explicit rule identifiers (like ρ 1 -ρ 5 used in Example 1) that stand for a specific rule. A mapping that becomes part of the specification assigns weighted rules to identifiers. This indirection allows us to use multiple rules with the same left-and right-hand side and even the same weight. In our composition constructions we use this facility to establish a more concise and simpler relation between the constructed rules of the composed xtt and the original rules of the input xtt. Definition 3. A weighted extended (top-down) tree transducer with rule identifiers is a system (Q, Σ, ∆, I, R, χ), where -Q, Σ, ∆, and I are the same as the corresponding elements of an xtt, -R is a finite set of rule identifiers, and

-χ : R → Q(T Σ (X)) × A × T ∆ (Q(X)
) is a rule assignment that maps each rule identifier ρ ∈ R to its content χ(ρ) = (l, a, r) such that {l, r} ⊆ Q(X), l is linear, and var(r) ⊆ var(l).

In accordance with our notation for rules, we often write l

a -→ r for elements (l, a, r) ∈ Q(T Σ (X)) × A × T ∆ (Q(X))
. Moreover, we let wt : R → A be such that wt(ρ) = a for all ρ ∈ R with χ(ρ) = l a -→ r. Intuitively, 'wt' maps a rule identifier to the weight of its identified rule.

The semantics of the xtt M = (Q, Σ, ∆, I, R, χ) with rule identifiers R is given by rewriting in essentially the same way as before. Let Σ and ∆ be two alphabets such that Σ ⊆ Σ and

∆ ⊆ ∆ and Q ∩ (Σ ∪ ∆ ) = ∅. Again, we call a position w ∈ pos Q (ξ) in a sentential form ξ ∈ T ∆ (Q(T Σ (X))) reducible (for M ) if there exists a rule ρ ∈ R with χ(ρ) = l a -→ r and a substitution θ : X → T Σ (X) such that ξ| w = lθ. Now, let ξ, ζ ∈ T ∆ (Q(T Σ (X))), ρ ∈ R, and χ(ρ) = l a -→ r.
We say that ξ rewrites to ζ using ρ, denoted by ξ ⇒ ρ M ζ, if there exists a substitution θ : X → T Σ (X) such that ξ| w = lθ and ζ = ξ[rθ] w where w is the least reducible position in pos Q (ξ) with respect to the lexicographic total order on IN * . The (extended) weighted relation τ M computed by M is given by

τ M (ξ, ζ) = ρ1,...,ρ k ∈R ξ⇒ ρ 1 M ;•••;⇒ ρ k M ζ k i=1 wt(ρ i ) for every ξ, ζ ∈ T ∆ (Q(T Σ (X))
). As for xtt, the semantics τ M of the xtt M with rule identifiers is the weighted relation τ M : T Σ × T ∆ → A such that τ M (t, u) = q∈I τ M (q(t), u) for every t ∈ T Σ and u ∈ T ∆ . The properties of rules and xtt defined in Sect. 2 generalize straightforwardly to xtt with rule identifiers.

Example 4. Let N = ({p}, Γ, ∆, {p}, R, χ) be the xtt with rule identifiers such that -Γ = {f, h, b} and ∆ = {λ, γ, δ, β}, -R = {µ 1 , . . . , µ 7 }, and the rule assignment χ is given by 6 shows a derivation from p(t) to u with weight

χ(µ 1 ) = p(x 1 ) 2 -→ γ(p(x 1 )) χ(µ 5 ) = p(h(x 1 )) 4 -→ δ(p(x 1 )) χ(µ 2 ) = p(f (x 1 , x 2 )) 2 -→ λ(p(x 1 ), p(x 2 )) χ(µ 6 ) = p(h(x 1 )) 4 -→ δ(p(x 1 )) χ(µ 3 ) = p(f (x 1 , x 2 )) 3 -→ λ(p(x 1 ), p(x 2 )) χ(µ 7 ) = p(b) 1 -→ β χ(µ 4 ) = p(f (x 1 , x 2 )) 5 -→ λ(β, λ(p(x 1 ), p(x 2 ))) . ε-rule consuming erasing producing linear nondeleting µ 1 µ 2 -µ 7 µ 1 -µ 7 µ 1 -µ 7 µ 1 -µ 7 Let t = f (h(h(b)), b) and u = λ(β, λ(δ(δ(β)), β)) as in Example 2. Figure
wt(µ 4 ) • wt(µ 5 ) • wt(µ 5 ) • wt(µ 7 ) • wt(µ 7 ) = 5 • 4 • 4 • 1 • 1 = 80 .
We can construct exactly three other derivations from p(t) to u using the rule sequences µ 4 µ 5 µ 6 µ 7 µ 7 , µ 4 µ 6 µ 5 µ 7 µ 7 , and µ 4 µ 6 µ 6 µ 7 µ 7 . All of these derivations have the same weight. Consequently, τ N (t, u) = 80 + 80 + 80 + 80 = 320. We can easily see that the two models of xtt are equally expressive. For every xtt (Q, Σ, ∆, I, R) we can construct an equivalent xtt (Q, Σ, ∆, I, R, χ) with rule identifiers by setting χ = id R , where id R is the identity on R. Conversely, given an xtt M = (Q, Σ, ∆, I, R, χ) with rule identifiers we can obtain an equivalent xtt (Q, Σ, ∆, I, R) by setting

R(l, r) = ρ∈R : χ(ρ)=(l,a,r) wt(ρ) (4)
for all l ∈ Q(T Σ (X)) and r ∈ T ∆ (Q(X)). 14 The construction is illustrated in Example 5. In this manner, we obtain exactly the xtt of Example 2, for which we only have one derivation from p(t) to u, which is shown in Fig. 3. Naturally, its weight is 320.

Composition with a Top-down Tree Transducer

In this section, we will discuss compositions τ M ;τ N for xtt M = (Q, Σ, Γ, I 1 , R 1 ) and N = (P, Γ, ∆, I 2 , R 2 ), in which the xtt N is actually a top-down tree transducer (tdtt). Moreover, we require that the xtt M does not have any ε-rules. This restriction ensures that the set {t | (s, t) ∈ supp(τ M )} is finite for every s ∈ T Σ [see [START_REF] Arnold | Morphismes et bimorphismes d'arbres[END_REF]] because each rule application consumes at least one input symbol. Hence there can only be finitely many rule applications to q(s) given a state q ∈ Q and an input tree s, which yields an upper bound on the number of potential derivations, which in turn limits the number of output symbols in each output tree. We already demonstrated in Sect. 3 that this restriction is sufficient to ensure that the sum over all intermediate trees t occurring in (2):

(τ M ; τ N )(s, u) = t∈T Γ τ M (s, t) • τ N (t, u)
is finite for all s ∈ T Σ and u ∈ T ∆ . Thus, composition is well-defined in all cases discussed in this section.

Construction

Now we are ready to present the generic composition construction. For the sake of uniformity, we will construct more rules than strictly necessary. As already indicated in Fig. 4, the states of the composed xtt will be pairs of states with one state from each input xtt. Next, let us fix an important constant m.

-Let c ≥ |pos x (r)| for all l → r ∈ R 2 and x ∈ X. Roughly speaking, c is larger than the maximal copying degree of N , which is the maximal number of times a variable occurs on some right-hand side of a rule of N . To keep the presentation simple, we assume that c ≥ 1. -Let s ≥ |pos Γ (r)| for all l → r ∈ R 1 . Consequently, s is larger than the maximal number of output symbols in a right-hand side of a rule of M . -Finally, let m ≥ c s . The constant m provides an upper bound to the number of steps required by N to process a right-hand side of a rule of M .

Recall that given a sentential form ξ ∈ T ∆ (P (T Γ (Q(T Σ (X))))) and a rule ρ ∈ R 1 there exists at most one 15 Naturally, the same property holds for the tdtt N . To avoid an explicit conversion, we identify elements of T ∆ (P (Q(T Σ (X)))) with elements of T ∆ ((P ×Q)(T Σ (X))) in the obvious manner. Finally, we let

ζ ∈ T ∆ (P (T Γ (Q(T Σ (X))))) such that ξ ⇒ ρ M ζ.
⇒ w N = (⇒ µ1 N ; • • • ; ⇒ µ k N ) if w = µ 1 • • • µ k with µ 1 , . . . , µ k ∈ R 2 .
Definition 6. The composed xtt M ; N is the xtt

(P × Q, Σ, ∆, I 2 × I 1 , R, χ) with rule identifiers R = { ρ, p, w | ρ ∈ R 1 , p ∈ P, w ∈ R * 2 , |w| ≤ m} such that χ( l → r, p, µ 1 • • • µ k ) = (p(l)
, a, r ) for every l → r ∈ R 1 , p ∈ P , and rule sequence µ 1 , . . . , µ k ∈ R 2 with k ≤ m, where r ∈ T ∆ (P (Q(X))) and

a = R 1 (l → r) • k i=1 R 2 (µ i ) if p(l) ⇒ (l,r) M ; ⇒ µ1•••µ k N r 0 otherwise.
Clearly, the construction might return a lot of rule identifiers whose associated rules have weight 0. These rules are useless, and we typically will not report them in our examples. Moreover, we can easily see that the constructed rules never have the forbidden shape l → r with {l, r} ⊆ P (Q(X)) because the left-hand side l equals p(l ) for some left-hand side l of a rule of M , which does not have ε-rules. Let us illustrate the construction on two example xtt, which we will use throughout this section.

Example 7. We again use the semiring of real numbers in this example. Moreover, let us consider the xtt M and N , which are given as follows:

M = ({q}, Σ, Σ, {q}, R 1 )
and

N = ({p 0 , p}, Σ, ∆, {p 0 }, R 2 ) ,
where -Σ = {γ, α} and ∆ = {σ} ∪ Σ, -R 1 contains the rules

ρ 1 : q(γ(x 1 )) 2 -→ γ(γ(q(x 1 ))) ρ 2 : q(α) 2 -→ α ,
and R 2 contains the rules

µ 1 : p 0 (γ(x 1 )) 4 -→ σ(p 0 (x 1 ), p 0 (x 1 )) µ 6 : p(γ(x 1 )) 1 -→ γ(p(x 1 )) µ 2 : p 0 (γ(x 1 )) 2 -→ σ(p 0 (x 1 ), p(x 1 )) µ 7 : p(γ(x 1 )) 3 -→ α µ 3 : p 0 (γ(x 1 )) 2 -→ σ(p(x 1 ), p 0 (x 1 )) µ 8 : p(α) 1 -→ α µ 4 : p 0 (γ(x 1 )) 1 -→ σ(p(x 1 ), p(x 1 )) µ 5 : p 0 (α) 1 -→ α . ε-rule consuming erasing producing linear nondeleting ρ 1 , ρ 2 ρ 1 , ρ 2 ρ 1 , ρ 2 ρ 1 , ρ 2 µ 1 -µ 8 µ 1 -µ 8 µ 5 -µ 8 µ 1 -µ 6 , µ 8
Both M and N are tdtt, M is linear and nondeleting, whereas N is neither linear nor nondeleting. Additionally, the xtt M is deterministic and total. We can set c = 2 and s = 2, and thus, we can select m = 4. To increase readability, 7. Derivation for rule ρ1, p, µ6µ7 (see Example 7).

p q γ x 1 ⇒ ρ1 M p γ γ q x 1 ⇒ µ6 N γ p γ q x 1 ⇒ µ7 N γ α Fig.
let R γ p0 = {µ 1 , µ 2 , µ 3 , µ 4 } and R γ p = {µ 6 , µ 7 }. Intuitively, R γ p0 and R γ p are the sets of rules that consume the input symbol γ in state p 0 and p, respectively. Now let us construct the composition M ; N . It is the xtt

M ; N = (Q , Σ, ∆, I , R, χ)
with rule identifiers such that

-Q = { p 0 , q , p, q } and I = { p 0 , q }, -R = { ρ 2 , p 0 , µ 5 , ρ 2 , p, µ 8 , ρ 1 , p, µ 6 µ 6 , ρ 1 , p, µ 6 µ 7 , ρ 1 , p, µ 7 } ∪ R with R = { ρ 1 , p 0 , µ 1 µµ | µ, µ ∈ R γ p0 } ∪ ∪ { ρ 1 , p 0 , µ 2 µµ | µ ∈ R γ p0 , µ ∈ R γ p } ∪ ∪ { ρ 1 , p 0 , µ 3 µµ | µ ∈ R γ p , µ ∈ R γ p0 } ∪ ∪ { ρ 1 , p 0 , µ 4 µµ | µ, µ ∈ R γ p } .
In total we have 5 + 16 + 8 + 8 + 4 = 41 (meaningful) rule identifiers. We will not present all 41 corresponding rules, but we will show two example rules to demonstrate the construction. Let us first construct the rule for the identifier ρ 1 , p, µ 6 µ 7 . To this end, we need to build a derivation starting at p(q(γ(x 1 ))) using the rule sequence ρ 1 µ 6 µ 7 . This derivation is illustrated in Fig. 7. We obtain the rule χ( ρ 1 , p, µ 6 µ 7 ) = p, q (γ(x 1 )), 2

• 1 • 3, γ(α) .
Secondly, let us construct the rule for the identifier ρ 1 , p 0 , µ 3 µ 7 µ 2 . This time we need to build a derivation that starts with p 0 (q(γ(x 1 ))) and uses the rule sequence ρ 1 µ 3 µ 7 µ 2 . We illustrate the derivation in Fig. 8. Consequently, we obtain the rule

χ( ρ 1 , p 0 , µ 3 µ 7 µ 2 ) = p 0 , q (γ(x 1 )), 2 • 2 • 3 • 2, σ(α, σ( p 0 , q (x 1 ), p, q (x 1 ))) .
Our general composition construction allows us to compose an xtt with a tdtt. As we have seen, it closely follows the intuition provided in Sect. 3 and uses the xtt with rule identifiers that we introduced in Sect. 4. This has the benefit

p 0 q γ x 1 ⇒ ρ1 M p 0 γ γ q x 1 ⇒ µ3 N σ p γ q x 1 p 0 γ q x 1 ⇒ µ7 N σ α p 0 γ q x 1 ⇒ µ2 N σ α σ p 0 q x 1 p q x 1
Fig. 8. Derivation for rule ρ1, p0, µ3µ7µ2 (see Example 7).

that we can obtain a direct correspondence between rule sequences of the xtt M and N and a rule in the composed xtt M ; N . In the standard xtt (without rule identifiers) this direct correspondence is lost since several derivations might create the same rule. 16Naturally, we would expect that the composed xtt M ; N computes the weighted tree transformation τ M ; τ N ; i.e., the composition of the weighted tree transformations computed by M and N . In other words, we hope that τ M ;N = τ M ; τ N . Although the rule aggregation and intertwining approach followed in the construction (and shown in Sect. 3) is reasonable, it fails to produce a correct xtt (i.e., an xtt that computes τ M ; τ N ) in a number of cases. This is already true in the unweighted case [START_REF] Engelfriet | Bottom-up and top-down tree transformations: A comparison[END_REF][START_REF] Baker | Composition of top-down and bottom-up tree transductions[END_REF] and the presence of weights adds a few more problematic cases, which we will discuss in the next section.

Correctness

In this section, we will investigate in which cases the composition construction (see Definition 6) actually produces an xtt that computes the composition τ M ;τ N . In principle, the xtt M need not be a tdtt, but for the following discussion we assume that it is. The generalization to the general case is simple in almost all cases (see [START_REF] Maletti | The power of extended top-down tree transducers[END_REF][START_REF] Engelfriet | Composition and decomposition of extended multi bottom-up tree transducers[END_REF] for a few notable differences). Consequently, let us look at compositions of tdtt. Top-down tree transducers have been studied quite extensively in the unweighted case (see [START_REF] Gécseg | Tree Automata[END_REF][START_REF] Gécseg | Tree languages[END_REF][START_REF] Comon | Tree automata techniques and applications[END_REF] for an overview). The following two slogans are known to represent properties that are unavailable in a single tdtt [START_REF] Engelfriet | Bottom-up and top-down tree transformations: A comparison[END_REF][START_REF] Baker | Composition of top-down and bottom-up tree transductions[END_REF]:

-Nondeterminism followed by copying (non-linearity), and -Checking (non-totality) followed by deletion.

A composition τ M ; τ N of two tdtt M and N can implement both properties mentioned in the slogans. Thus, these properties already restrict the potential successful compositions of tdtt. In fact, in all remaining cases shown in Table 1 the composition of the tdtt M and N is possible in the unweighted case [5, Theorem 1]. A detailed explanation of those restrictions on compositions is presented in [START_REF] Engelfriet | Bottom-up and top-down tree transformations: A comparison[END_REF][START_REF] Baker | Composition of top-down and bottom-up tree transductions[END_REF]. Here we will focus on the particular problems that occur in the generalization of those results to the weighted case because the limitations on compositions in the unweighted case transfer immediately to our setting. 17 Thus, we will not investigate compositions that do not fulfill the requirements in Table 1. 18 Case (a) has been partially generalized in [START_REF] Kuich | Full abstract families of tree series I[END_REF]Theorem 2.4] to weighted tdtt. More precisely, it was shown that the composition succeeds if both M and N are linear and nondeleting. 19 This result was further (partially) generalized in [14, Theorem 5.18], which covers the case in which M and N are deterministic and only N is linear and nondeleting. Finally, [START_REF] Maletti | Compositions of tree series transformations[END_REF]Theorem 26] presents the full generality and matches Case (a) of the unweighted setting exactly.

Theorem 8 (see [START_REF] Maletti | Compositions of tree series transformations[END_REF]Theorem 26]). If the tdtt N is linear and nondeleting, then τ M ;N = τ M ; τ N .

Case (b) is slightly problematic in the weighted setting, and the only known generalizations are actually instances of Case (d). Let us illustrate the problem. The tdtt N can delete an intermediate subtree t that was output by M as the result of processing an input subtree s . In the composed tdtt, the input subtree s is deleted right away without processing it. This phenomenon is abstractly illustrated in Fig. 9. In addition, we showcase a derivation using our example xtt of Example 7 in Fig. 10 (note that only linear rules of N are used in this derivation). Thus, the actual input subtree s and the intermediate subtree t are not relevant in the composed tdtt. In the unweighted setting, this independence is guaranteed by the totality of M , which yields that for each input tree s there exists a translation t of it. In other words, for each input tree s ∈ T Σ and state q ∈ Q, we have

t∈T Γ ρ1,...,ρ k ∈R1 q(s)⇒ ρ 1 M ;•••;⇒ ρ k M t k i=1 R 1 (ρ i ) = 1 .
17 More precisely, the restrictions only transfer to xtt over non-rings due to a result by Wang [START_REF] Wang | On characters of semirings[END_REF][START_REF] Wang | On rational series and rational languages[END_REF]. A ring is a semiring that has additive inverses; i.e., there exists an element -1 such that 1 + (-1) = 0. 18 Although such compositions can, in principle, succeed. Mind that the counterexamples of [START_REF] Engelfriet | Bottom-up and top-down tree transformations: A comparison[END_REF][START_REF] Baker | Composition of top-down and bottom-up tree transductions[END_REF] only generalize to non-rings. In fact, given a suitably strong ring, any composition becomes possible. 19 In fact, [START_REF] Kuich | Full abstract families of tree series I[END_REF] proves closure under composition for a slightly more general class, but the mentioned result can be obtained easily by instantiating the more general construction to our weighted tdtt model. Clearly, in the Boolean semiring, the previous equation is fulfilled if there is at least one derivation from q(s) to some t. To obtain a generalization of the requirement for the weighted setting, we observe that the composed tdtt also ignores the input subtree s. Definition 9. A state q ∈ Q is constant if there exists a semiring element a ∈ A such that for every s ∈ T Σ we have

t∈T Γ ρ1,...,ρ k ∈R1 q(s)⇒ ρ 1 M ;•••;⇒ ρ k M t k i=1 R 1 (ρ i ) = a . (5)
We also say that q is a-constant if q is constant using the semiring element a.

The xtt M is constant if all its states q ∈ Q are constant.

Note that the sums in ( 5) are always finite, which we already showed at the beginning of Sect. 5. Let us demonstrate some constant tdtt, in which all states are 1-constant. In general, different states of a constant tdtt can have different semiring elements for which they are constant.

Example 10. All of the following tdtt have only 1-constant states:

every total tdtt over the Boolean semiring, every Boolean and total tdtt over an idempotent semiring, and every deterministic, total, and Boolean tdtt over any semiring.

Clearly, the total tdtt M of Example 7 is not constant, which is also shows that a total tdtt is not necessarily constant. If the tdtt M is constant, then we can perfectly predict the missing weight b in the derivation of the composed tdtt in Fig. 9 and charge it for the rule that actually performs the deletion. 20 Note that our presented composition construction (see Definition 6) might fail, but the authors believe that it can be modified as indicated to obtain the following result.

Conjecture 11. If the xtt M is constant and the tdtt N is linear, then τ M ; τ N can be computed by an xtt.

Note that Conjecture 11 covers all the cases (for M ) mentioned in Example 10. It remains to be determined whether the indicated adjustment actually works. Moreover, depending on the semiring, it might be difficult to determine whether a state is constant, so additional syntactic requirements that lead to constant states (potentially with a weight different from 0 and 1) would be desirable.

Case (c) is also problematic and has not been addressed in the literature. This is due to the fact that an intermediate output tree t can be copied by N . Composition:

s s a•b = = ⇒ M t t c•d•e = == ⇒ N u u u Composed tdtt: s s a•b 2 •c•d•e = ===== ⇒ M ;N u u u
Fig. 11. Another difference between composition and the composed tdtt. Atop the arrow we mark the weight and next to it the tdtt, in which the derivation happens. More precisely, weight a is charged for processing s (without s ), weight b is charged for processing s , weight c is charged for processing t (without t ), and weights d and e are charged for processing t (producing u and u , respectively).

In the composition, the weight charged for generating the tree t from an input subtree s is charged once, but in the composed tdtt this weight is charged twice since the input subtree s will be copied and processed twice. The process is illustrated in Fig. 11. In addition, we provide derivations using the xtt of Example 7 that demonstrate the phenomenon in Fig. 12 (note that the tdtt M of Example 7 is deterministic and we only used nondeleting rules of N in these derivations).

So again our generic composition construction (see Definition 6) might fail, but contrary to the previous case, the authors believe that this can be addressed without any further requirement. Instead of using the original state of M in all copies, the authors propose to use the corresponding state from an unweighted copy of M in all but one copies. Thus, the weight that M charges for processing the input tree would only be charged in the single copy and the other copies, which run using the unweighted copy of M , do not cause additional charges for processing the input. Since the input tdtt M is deterministic, we know that the copies will behave equally in all aspects besides the weight that they charge. Let us provide some detail.

Definition 12. An unweighted copy of M is a Boolean xtt (Q, Σ, Γ, I 1 , R 1 ) such that l → r ∈ R 1 ⇐⇒ l → r ∈ R 1 .
We will not formalize the modified construction, but we will present the essential steps. First, we take the (disjoint) union of M and an unweighted copy M of M (by renaming all states of the copy from q to q). Let us assume that a state q ∈ Q corresponds to a state q in M , and similarly, a rule ρ ∈ R 1 corresponds to a rule ρ in M . When processing a rule in which the tdtt N copies, we modify all but one copies to use the corresponding state from M . Let Composition: 4 . The additional weight R1(ρ2) 3 = 2 3 is charged by M ; N for processing the input subtree α (using ρ2) three more times.

p 0 q γ α ⇒ ρ1 M p 0 γ γ q α ⇒ ρ2 M p 0 γ γ α ⇒ µ1
R1(ρ1) • R1(ρ2) • R2(µ1) 3 • R2(µ5) 4 = 2 • 2 • 4 3 • 1 4 , whereas the composed tdtt charges 2 • 4 3 • (2 • 1)
us illustrate this adjustment on an example rule of Example 7. Figure 13 shows the original and the modified derivation that lead to the rule ν = ρ 1 , p 0 , µ 3 µ 6 µ 1 of M ; N and our new rule χ(ν) = p 0 , q (γ(x 1 )), 16, σ(γ( p, q (x 1 )), σ( p 0 , q (x 1 ), p 0 , q (x 1 )))

χ (ν) = p 0 , q (γ(x 1 )), 16, σ(γ( p, q (x 1 )), σ( p 0 , q (x 1 ), p 0 , q (x 1 ))) .

Figure 14 shows the modified derivation corresponding to the derivation of the composed tdtt, which is displayed in Fig. 12.

Original derivation:

p 0 q γ x 1 ⇒ ρ1 M p 0 γ γ q x 1 ⇒ µ3 N σ p γ q x 1 p 0 γ q x 1 ⇒ µ6 N σ γ p q x 1 p 0 γ q x 1 ⇒ µ1 N σ γ p q x 1 σ p 0 q x 1 p 0 q x 1
Modified derivation:

p 0 q γ x 1 ⇒ ρ1 M p 0 γ γ q x 1 ⇒ µ3 N σ p γ q x 1 p 0 γ q x 1 ⇒ µ6 N σ γ p q x 1 p 0 γ q x 1 ⇒ µ1 N σ γ p q x 1 σ p 0 q x 1 p 0 q x 1
Fig. 13. Two derivations that yield rules. The upper one follows our composition construction, whereas the lower one is adjusted to address the problem of Case (c). We boxed the states that are adjusted due to copying of N . We selected to mark the left copies, but the choice is arbitrary.

Conjecture 13. If the xtt M is deterministic and the tdtt N is nondeleting, then τ M ; τ N can be computed by an xtt.

Finally, Case (d) is essentially a combination of Cases (b) and (c). This case was first addressed by [START_REF] Engelfriet | Bottom-up and top-down tree series transformations[END_REF]Theorem 5.18], in which it was shown that a Boolean, deterministic, and total tdtt M can be composed with a deterministic tdtt N . A similar statement was obtained in [START_REF] Maletti | Compositions of tree series transformations[END_REF]Theorem 30], where (i) the same

p 0 , q γ α ⇒ ρ1,p0,µ1µ1µ1 M ;N σ σ p 0 , q α p 0 , q α σ p 0 , q α p 0 , q α ⇒ ρ 2 ,p0,µ5 M ;N σ σ α p 0 , q α σ p 0 , q α p 0 , q α ⇒ ρ 2 ,p0,µ5 M ;N σ σ α α σ p 0 , q α p 0 , q α ⇒ ρ 2 ,p0,µ5 M ;N σ σ α α σ α p 0 , q α ⇒ ρ2,p0,µ5 M ;N σ σ α α σ α α
Fig. 14. Derivation using the new rules (see Fig. 12). The derivation now correctly charges the weight

R 1 (ρ1) • R 2 (µ1) 3 • R2(µ5) 4 • R 1 (ρ2) • R 1 (ρ2) 3 = 2 • 4 3 • 1 4 • 2 • 1 3 because overlined rules charge weight 1.
restrictions are placed on M and (ii) N is required to be linear. The result of [START_REF] Maletti | Compositions of tree series transformations[END_REF] clearly avoids the problematic Case (c) by requiring N to be linear. The result of [START_REF] Engelfriet | Bottom-up and top-down tree series transformations[END_REF] allows non-linear tdtt N , and it could thus be reasoned that they also had to handle the problematic Case (c). However, the requirement that the tdtt M is Boolean already enforces that the additional weights (see Figs. 11 and12) charged by the composed tdtt (constructed according to the general composition construction of Definition 6) are all 1. Thus, no modification was necessary under their assumptions. Using the indicated improvements suggested in Cases (b) and (c), the authors conjecture the following result, which covers both known results. Essentially, the authors believe that a constant and deterministic xtt M can be composed with any tdtt N .

Conjecture 14.

If the xtt M is constant and deterministic and N is a tdtt, then τ M ; τ N can be computed by an xtt.

This concludes our investigation of compositions of tdtt. Table 2 shows the various results obtained in the weighted case. It is interesting that if Conjectures 11, 13, and 14 were true, then we would recover the beautiful symmetry that is present in the composition results [START_REF] Engelfriet | Bottom-up and top-down tree transformations: A comparison[END_REF][START_REF] Baker | Composition of top-down and bottom-up tree transductions[END_REF] for unweighted top-down and bottomup tree transducers [START_REF] Thatcher | Tree automata: An informal survey[END_REF] also in the weighted case. A summary of the composition results for weighted bottom-up tree transducers [START_REF] Engelfriet | Bottom-up and top-down tree series transformations[END_REF] can be found in Table 3, but the reader is refered to [START_REF] Engelfriet | Bottom-up and top-down tree series transformations[END_REF][START_REF] Maletti | Compositions of tree series transformations[END_REF][START_REF] Maletti | The Power of Tree Series Transducers[END_REF] for the detailed results.

Allowing ε-rules

This section is devoted to compositions of tree transformations computed by xtt M and N , of which the xtt N is a top-down tree transducer with ε-rules [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF]. Roughly speaking, a top-down tree transducer with ε-rules is an xtt, in which simple and ε-rules are allowed. In other words, this section investigates the effect of ε-rules in N to the results of Sect. 5. In the unweighted setting, this scenario was investigated in [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF], and we essentially report the results of [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF], which we adjusted to our weighted setting. Let us start with the formal definition of the requirements of this section. For the rest of this section, let M = (Q, Σ, Γ, I 1 , R 1 ) and N = (P, Γ, ∆, I 2 , R 2 ) be the xtt that we want to compose. -

The xtt M is shallow if |pos Γ (r)| ≤ 1 for every l → r ∈ R 1 . -The xtt N is a tdtt with ε-rules if |pos Γ (l)| ≤ 1 for every l → r ∈ R 2 .
Clearly, each tdtt is a tdtt with ε-rules, but a tdtt need not be shallow. Let us examine these properties for the xtt in our examples. Now we can formally define the goal of this section. We will investigate compositions of xtt M and N such that M is shallow and N is a tdtt with [33, Theorem 24] constant, det., [total] conjectured ε-rules. To show that the condition that ensures well-definedness of the sum in the definition (2) of composition does not influence the results much, we additionally assume here that N does only have producing rules. In this case, there can only be finitely many rule applications generating the output tree u, which limits the size of the intermediate tree [see [START_REF] Arnold | Morphismes et bimorphismes d'arbres[END_REF]]. Thus, all compositions are well-defined in the cases of this section.

Construction

Before we present an adaptation of the generic construction in Sect. 5.1, let us demonstrate that the generic construction fails to handle ε-rules of N in a meaningful manner. Thus, we need to adjust our construction. To avoid the problem in the lower derivation of Fig. 15, we restrict the rules of N that can be used when processing the right-hand side r of a rule ρ ∈ R 1 . As in [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF] we require that r is processed only with consuming rules of N . The ε-rules of N need to fire either before ρ or after all intermediate symbols of r are fully consumed by N . This creates a problem, if the rule ρ creates 2 intermediate symbols at the same time, and the original derivation uses ε-rules after consuming one intermediate symbol but before consuming the second intermediate symbol. To avoid this problem, we already assumed in this section that M is shallow. Consequently, m = 1 provides an upper bound to the number of consuming rules required by N to process the right-hand side of a rule of M . This is due to the fact that there is at most one intermediate symbol in any right-hand side of a rule of M , and we can only use consuming rules of N to process it. As before, for any sentential form ξ ∈ T ∆ (P (T Γ (Q(T Σ (X))))) and rule ρ ∈ R there exists at most one ζ ∈ T ∆ (P (T Γ (Q(T Σ (X))))) such that ξ ⇒ ρ M ζ, which also holds for the xtt N . Similarly, we recall that we identify elements of T ∆ (P (Q(T Σ (X)))) with elements of T ∆ ((P × Q)(T Σ (X))) in the obvious manner.

Definition 17 (cf. [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF]Definition 9]). The ε-composition M ; ε N of M and N is the xtt

(P × Q, Σ, ∆, I 2 × I 1 , R, χ) with rule identifiers R = { ρ, p, ε | erasing ρ ∈ R 1 , p ∈ P } ∪ ∪ { ρ, p, µ | producing ρ ∈ R 1 , p ∈ P, consuming µ ∈ R 2 } ∪ ∪ { ε, q, µ | q ∈ Q, ε-rule µ ∈ R 2 }
such that χ( l → r, p, ε ) = (p(l), R 1 (l → r), p(r)) for every erasing rule l → r ∈ R 1 and p ∈ P , χ( l → r, p, µ ) = (p(l), a, r ), where

a = R 1 (l → r) • R 2 (µ) if p(l) ⇒ (l,r) M ; ⇒ µ N r 0 otherwise
for every producing l → r ∈ R 1 , p ∈ P , and consuming µ ∈ R 2 , and χ( ε, q, l → r ) = (lθ, R 2 (l → r), rθ), where θ(x) = q(x) for every x ∈ X, q ∈ Q, and ε-rule l → r ∈ R 2 .

Note that the only differences to the construction of [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF] are the presence of (i) non-simple left-hand sides in rules of M and (ii) weights. Let us discuss the three sets of rule identifiers mentioned in Definition 17. Rule identifiers of the form ρ, p, ε refer to variants of an erasing rule ρ of R 1 . For each state p ∈ P , we obtain a variant by annotating the two states (in the left-and right-hand side) by p. In other words, we perform a step using M , but since no intermediate symbol is produced, we do not perform a step using N . Second, the rule identifiers of the form ρ, p, µ contain rules that are obtained in the usual way by processing the right-hand side of a producing rule of M by consuming rules of N . Since M is shallow and N is a tdtt with ε-rules, each producing rule of M contains exactly one intermediate symbol and each consuming rule of N contains exactly one intermediate symbol. Thus, the derivation only succeeds if the producing rule of M produces exactly the symbol that the consuming rule of N consumes. These two types of rules were also present in the generic composition construction of Sect. 5.1. Finally, rule identifiers of the form ε, q, µ refer to a variant of an ε-rule µ of N that is annotated with the state q ∈ Q.

Let us quickly check whether the obtained rules l → r are admissable; i.e., whether {l, r} ⊆ P (Q(X)). Clearly, identifiers of the form ρ, p, ε yield admissable rules because they contain just copies of rules of M . The same reasoning applies to rules with identifiers of the form ε, q, µ , which are copies of rules of N . Finally, rules with identifiers like ρ, p, µ are always producing because each rule µ ∈ R 2 is producing. Clearly, producing rules are admissable. Next, let us illustrate the construction.

Example 18. Let M = ({q 0 , q 1 }, Σ, Γ, {q 0 }, R) and N = ({p}, Γ, ∆, {p}, R ) be the xtt of Examples 1 and 2, respectively. The composition construction of Definition 17 yields the xtt M ; ε N = (P ×Q, Σ, ∆, { p, q 0 }, R, χ) with rule identifiers

R = { ρ 2 , p, ε , ρ 1 , p, µ 2 , ρ 1 , p, µ 3 , ρ 3 , p, µ 5 , ρ 4 , p, µ 4 , ρ 5 , p, µ 4 , ε, q 0 , µ 1 , ε, q 1 , µ 1 } such that χ( ρ 2 , p, ε ) =
p, q 0 (σ(α, x 1 ))

3

-→ p, q 0 (x 1 ) χ( ρ 1 , p, µ 2 ) = p, q 0 (σ(σ(x 1 , x 2 ), α))

2•5
-→ λ( p, q 1 (x 1 ), p, q 0 (x 2 )) χ( ρ 1 , p, µ 3 ) = p, q 0 (σ(σ(x 1 , x 2 ), α)) -→ λ(β, λ( p, q 1 (x 1 ), p, q 0 (x 2 )))

χ( ρ 3 , p, µ 5 ) = p, q 0 (α)

1•1 -→ β χ( ρ 4 , p, µ 4 ) = p, q 1 (x 1 ) 2•8 -→ δ( p, q 0 (x 1 )) χ( ρ 5 , p, µ 4 ) = p, q 1 (x 1 ) 5•8 -→ δ( p, q 1 (x 1 )) χ( ε, q 0 , µ 1 ) = p, q 0 (x 1 ) 2 -→ γ( p, q 0 (x 1 )) χ( ε, q 1 , µ 1 ) = p, q 1 (x 1 ) 2 -→ γ( p, q 1 (x 1 )) .
The construction of the rule corresponding to the rule identifier ρ 1 , p, µ 2 is illustrated in Fig. 16.

Correctness

Let us start by recalling the two cases, in which the composition construction of [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF], of which our construction in Definition 17 is an adaptation, is successful in the unweighted setting. Recall that M is shallow and N is a tdtt with ε-rules. -N is linear, and -M is total or N is nondeleting, then τ M ; τ N can be computed by an xtt [START_REF] Maletti | Compositions of top-down tree transducers with ε-rules[END_REF]Theorem 17]. Table 4 shows these two cases, which correspond to the equally named cases in Sect. 5. Let us start with Case (a). As in the previous section, this case does not cause further problems in the weighted setting, and we will sketch the correctness proof for our composition construction of Definition 17.

If p q 0 σ σ x 1 x 2 α ⇒ ρ1 M p f q 1 x 1 q 0 x 2 ⇒ µ2 N λ p q 1 x 1 p q 0 x 2
Theorem 19. If M is shallow and N is a linear and nondeleting tdtt with ε-rules, then τ M ;εN = τ M ; τ N . Proof (sketch). Let ξ ∈ P (Q(T Σ )) and u ∈ T ∆ . We claim that there is a weightpreserving bijection between the derivations of the form

ξ (⇒ ρ1 M ; • • • ; ⇒ ρ k M ) ; (⇒ µ1 N ; • • • ; ⇒ µn N ) u ,
and the derivations of the form ξ ⇒ ν1 M ;εN ; • • • ; ⇒ ν M ;εN u. We construct the bijection by induction on k. Let s ∈ T Σ , p ∈ P , and q ∈ Q be such that ξ = p(q(s)). Next, we distinguish whether the first applied rule ρ 1 is erasing. If it is, then we start the derivation using M ; ε N with the rule ρ 1 , p, ε , which has the same weight as ρ 1 . Otherwise, the rule ρ 1 produces exactly one intermediate symbol γ ∈ Γ that will be consumed by exactly one rule µ i for some i ∈ IN. The symbol γ is consumed by exactly one rule because N is linear and nondeleting. Clearly, all rules µ 1 , . . . , µ i-1 before µ i must be ε-rules because otherwise they would consume the symbol γ. In M ; ε N we simulate this derivation by starting with the ε-rules ε, q, µ 1 , . . . , ε, q, µ i-1 followed by the consuming rule ρ 1 , p , µ i , where p is the (unique) state that occurs in the right-hand side of the rule µ i-1 . 22 Clearly, this part of the derivation has the same weight as the product of the weight of rule ρ 1 and the weights of the rules µ 1 , . . . , µ i . Now we covered all three cases and shortened the derivation using M . The remainder of the derivation can then be processed using the induction hypothesis. Thus, our construction relates derivations bijectively and preserves the weight. Given this bijective and weight-preserving relation, the main statement follows trivially. be an input and output tree for M as in Example 1. Figure 2 shows a derivation d M with weight 180 from q 0 (s) to t using M . Moreover, let

u = λ(β, λ(δ(δ(β)), γ(γ(β)))) .
Figure 17 shows a derivation d N with weight 5

• 8 2 • 1 • 2 2 • 1 = 1 280 from p(t)
to u using N . The concatenation of the two derivations gives us a derivation d from p(q 0 (s)) to u using rules of M and N . Clearly, the weight of this derivation is 180 • 1 280 = 230 400. The image of the derivations d M and d N by the bijection constructed in the proof of Theorem 19 is shown in Fig. 18. The first four rules in the derivation d M are producing, and the produced symbol is immediately consumed in the corresponding step in the derivation d N . The fifth and sixth rules in the derivation d M are erasing rules, which are simulated by the corresponding erasing rules in the derivation d. The last rule in the derivation d M is another producing rule, whose produced symbol b is not immediately consumed in the current step of the derivation d N . Rather the ε-rule µ 1 is applied twice before rule µ 5 consumes the symbol b. Consequently, we have to defer the application of the rule ρ 3 , p, µ 5 to first allow the applications of the rule ε, q 0 , µ 1 . The following table lists the rule applications for all three derivations and shows the correspondence.

Step

1 2 3 4 5 6 7 d M : ρ 1 ρ 5 ρ 4 ρ 3 ρ 2 ρ 2 ρ 3 d N : µ 3 µ 4 µ 4 µ 5 µ 1 µ 1 µ 5 d: ρ 1 , p, µ 3 ρ 5 , p, µ 4 ρ 4 , p, µ 4 ρ 3 , p, µ 5 ρ 2 , p, ε ρ 2 , p, ε ε, q 0 , µ 1 ε, q 0 , µ 1 ρ 3 , p, µ 5
The weight of the derivation d is

(2 • 5) • (5 • 8) • (2 • 8) • (1 • 1) • 3 • 3 • 2 • 2 • (1 • 1) = 230 400 ,
which coincides with the expected result.

Let us move on to Case (b), in which we experience the same problem with deleted subtrees as in Sect. 5. We refer the reader to the discussion of Case (b) in Sect. 5 for an illustration of the problem and examples. Here, we avoid the problem by requiring (i) that the xtt M is Boolean and (ii) that the semiring A is idempotent (i.e., 1 + 1 = 1). This yields that the xtt M is essentially unweighted and constant (with weight 1). We observe that τ M (s, t) = 1 for all (s, t) ∈ supp(τ M ) because M is Boolean and A is idempotent, and for every s ∈ T Σ there exists t ∈ T Γ such that (s, t) ∈ supp(τ M ) due to the totality of M . next step we drop all mutilated rules from the rule sequence ρ 1 • • • ρ k and relate the obtained rule sequence in the same way as in the proof of Theorem 19 to the derivation of the composed xtt. The obtained derivation using the composed xtt has the same weight as the original derivation because we only dropped rules of R 1 , which have weight 1 because M is Boolean. It is not difficult to see that this mapping is surjective because we can always recover one subderivation for parts that we dropped due to the totality of M . This approach is illustrated in an example following the proof. Now we complete the proof as follows:

(τ M ; τ N )(ξ, u) = ρ1,...,ρ k ∈R1 µ1,...,µn∈R2 ξ(⇒ 19, which is a minor variation of Fig. 10. Figure 19 displays two derivations that we want to relate. Obviously, the rule sequence of M is ρ 1 ρ 1 ρ 2 . Now we need to mutilate the rules in the rule sequence. We start with the most aggressive attempt and mutilate every rule in the sequence to obtain ρ 1 ρ 1 ρ 2 . Figure 20 shows that the derivation is no longer successful for this rule sequence. Thus, we try the sequence ρ 1 ρ 1 ρ 2 , which indeed still delivers a successful derivation as depicted in Fig. 20. Next, we reduce the sequence by taking out all mutilated rules. We obtain just ρ 1 . Now we combine the producing rule ρ 1 as usual with the consuming rule µ 7 of the second rule sequence and relate them to the rule ρ 1 , p, µ 7 of the composed tdtt.

Following the ideas of Sect. 5, the authors suspect that instead of idempotence and a total and Boolean xtt M , we can simply require that M is constant. This leads to our final conjecture, which would generalize Theorem 21. We collect all obtained results of this section in Table 5. Testing two mutilated sequences. The upper one is too aggressive and the rule µ7 of N is not applicable anymore. The lower sequence represents the sought sequence because the derivation is still successful. After the deletion of the mutilated rules, we thus obtain just ρ1.

Fig. 1 .

 1 Fig. 1. The rules of the xtt M (see Example 1).

Fig. 3 .

 3 Fig. 3. A derivation from p(t) to u in N (see Example 2).

Fig. 4 .

 4 Fig. 4. Intertwined derivation from p(q0(s)) to u in M and N (see Examples 1 and 2).

Fig. 5 .

 5 Fig. 5. Composed rule constructed from ρ1 and µ3 of Examples 1 and 2.

Fig. 6 .

 6 Fig. 6. One possible derivation from p(t) to u in N of Example 4.

Example 5 .

 5 Let N be the xtt with rule identifiers of Example 4. To obtain an equivalent xtt N = (Q, Γ, ∆, I, R), we merge the rules µ 2 and µ 3 to form the rule p(f (x 1 , x 2 )) 2+3 --→ λ(p(x 1 ), p(x 2 )), merge the rules µ 5 and µ 6 to form the rule p(h(x 1 )) 4+4 --→ δ(p(x 1 )), and keep the rules µ 1 , µ 4 , and µ 7 with their original weight.

Fig. 9 .Fig. 10 .

 910 Fig.9. Difference between composition and the composed tdtt. Atop the arrows we mark the weight and next to it the tdtt, in which the derivation happens. More precisely, weight a is charged for processing s (without s ), weight b is charged for processing s , and weight c is charged for processing t (without t ).

Fig. 12 .

 12 Fig. 12. Difference between composition and the composed tdtt on the tdtt M and N of Example 7. The composition (upper display) charges the weightR1(ρ1) • R1(ρ2) • R2(µ1) 3 • R2(µ5) 4 = 2 • 2 • 4 3 • 1 4 , whereas the composed tdtt charges 2 • 4 3 • (2 • 1)4 . The additional weight R1(ρ2) 3 = 2 3 is charged by M ; N for processing the input subtree α (using ρ2) three more times.

Definition 15 (

 15 cf. [15, Definition 4] and [39, Definition 1]).

  xtt tdtt with ε-rules shallow M of Example 1 no (due to rule ρ 1 ) yes N of Example 2 yes no (due to rule µ 3 ) M of Example 7 yes (because it is a tdtt) no (due to rule ρ 1 ) N of Example 7 yes (because it is a tdtt) yes

Example 16 .Fig. 15 .

 1615 Fig.[START_REF] Engelfriet | Extended multi bottom-up tree transducers[END_REF]. Two derivations using the xtt M and N of Examples 1 and 2. The upper derivation cannot be simulated by M ;N since it starts with a rule of N . In principle, an unbounded number of rule applications of rule µ1 could happen before the intermediate symbol b is consumed in the lower derivation. Thus, such derivations can, in general, also not be simulated by M ; N .

Fig. 16 .

 16 Fig. 16. Construction of the rule with identifier ρ1, p, µ2 in Example 18.

  Let us illustrate the construction used in the proof of Theorem 19. Example 20. Let M and N be the xtt of Examples 1 and 2, and recall that M ; ε N is shown in Example 18. Moreover, let s = σ(σ(α, σ(α, σ(α, α))), α) and t = f (h(h(b)), b)

Fig. 17

 17 Fig.17. A derivation from p(t) to u using N (seeExample 20).

  Fig.17. A derivation from p(t) to u using N (seeExample 20).

  Fig.17. A derivation from p(t) to u using N (seeExample 20).

Theorem 21 . 1 MFig. 18 .

 21118 Fig.[START_REF] Fülöp | Hierarchies of tree series transformations. Theoret[END_REF]. The matching derivation from p, q0 (s) to u using M ;ε N (seeExample 20).

R 2 1 M 1 M

 211 (µ i ) = ν1,...,ν ∈R d : ξ⇒ ν ;εN ;•••;⇒ ν M ;εN u d ∈f -1 (d) i=1 wt(ν i ) (because the second sum is never empty due to surjectivity of f ) = ν1,...,ν ∈R ξ⇒ ν ;εN ;•••;⇒ ν M ;εN u i=1 wt(ν i ) = τ M ;εN (ξ, u) because A is idempotent and f -1 (d) = ∅. Thus, we conclude that M ; ε N computes τ M ; τ N . Let us illustrate the construction in the proof of Theorem 21 on an example. Example 22. Let us consider Fig.

Conjecture 23 .Fig. 19 .

 2319 Fig. 19. Relating rule sequences.

  and demonstrate their properties in the following table. Since all rules are linear and nondeleting, the xtt M is linear and nondeleting.

	ε-rule	consuming	erasing	producing	linear	nondeleting
	ρ 4

Table 1 .

 1 Cases for unweighted tdtt composition.

	Case	M	N
	(a)		linear and nondeleting
	(b)	total	linear
	(c)	deterministic	nondeleting
	(d)	deterministic and total

Table 2 .

 2 Composition results for weighted tdtt ('nondel.' abbreviates 'nondeleting' and 'det.' abbreviates 'deterministic').

	Case	M	N	Reference
	(a)	linear and nondel.	linear and nondel.	[31, Theorem 2.4]
		deterministic	det., linear, nondel.	[14, Theorem 5.18]
			linear and nondel.	[33, Theorem 26]
	(b)	constant	linear	Conjecture 11
	(c)	deterministic	nondeleting	Conjecture 13
	(d)	Boolean, det., total	deterministic	[14, Theorem 5.18]
		Boolean, det., total	linear	[33, Theorem 30]
		constant and det.		Conjecture 14

Table 3 .

 3 Composition results for weighted bottom-up tree transducers[START_REF] Engelfriet | Bottom-up and top-down tree series transformations[END_REF] ('nondel.' abbreviates 'nondeleting' and 'det.' abbreviates 'deterministic') for comparison. Note that every weighted bottom-up tree transducer can be made total.

	Case	M	N	Reference
	(a)	linear, nondel.	linear and nondel.	[31, Theorem 2.4]
		linear, nondel.	homomorphism	[14, Corollary 5.5]
		linear, nondel.		[33, Theorem 13]
	(b)	linear	[total]	[33, Theorem 20]
	(c)	nondeleting	Boolean, deterministic	[33, Theorem 24]
		nondeleting	constant, deterministic	conjectured
	(d)		Boolean, homomorphism	[14, Corollary 5.5]
			Boolean, det., [total]

Table 4 .

 4 Cases for unweighted xtt composition of M and N , where M is shallow and N is a tdtt with ε-rules.

	Case	M	N	Reference
	(a)		linear and nondeleting	[39, Theorem 17]
	(b)	total	linear	[39, Theorem 17]

Table 5 .

 5 Cases for weighted xtt composition, where M is a shallow xtt and N is a tdtt with ε-rules. In the second line (which uses Theorem 21), we additionally need to require that the semiring is idempotent.

	Case	M	N	Reference
	(a)		linear and nondeleting	Theorem 19
	(b)	total and Boolean	linear	Theorem 21
		constant	linear	Conjecture 23

These are actually unranked trees, but our operational tree transformation model will only have finitely many rules that prescribe (and limit) the ranks of symbols, so that we could have used a ranked alphabet as well.

A benefit of our approach without explicit ranks for symbols is that we can always take the union of two alphabets.

By distributivity, this yields a + a = a for all a ∈ A.

The powerset P(S) of a set S is the set of its subsets; i.e., P(S) = {U | U ⊆ S}.

The restriction {l, r} ⊆ Q(X), which is not present in[START_REF] Maletti | Survey: Weighted extended top-down tree transducers -Part I: Basics and expressive power[END_REF], disallows rules of the form (q(xi), p(xi)). This additional restriction is necessary because we do require complete semirings[START_REF] Hebisch | Semirings -Algebraic Theory and Applications in Computer Science[END_REF][START_REF] Golan | Semirings and their Applications[END_REF], which yields that we have to avoid infinite summations.

The name 'erasing' is justified by the fact that each erasing rule is consuming.

The sum (4) returns 0, as desired, if M has no rules with left-hand side l and righthand side r.

The interested reader can compare our construction to[START_REF] Maletti | Compositions of tree series transformations[END_REF][START_REF] Maletti | The Power of Tree Series Transducers[END_REF].

In fact, we can only predict the aggregated weight (as opposed to the weights of single deleted derivations), but that is sufficient.

If i = 1, then we let p = p.