Two or three things I know about tree transducers
Lê Thành Dũng Nguyên

MARAGS: A Multi-Adapter System for Multi-Task Retrieval Augmented Generation Question Answering
    Mitchell DeHaven
    
School of Physics, Nankai University, Tianjin, 300071, China 

===============================================================================================



§ ABSTRACT 
  You might know that the name tree transducers refers to various kinds of automata that compute functions on ranked trees, i.e. terms over a first-order signature. But have you ever wondered about:
  
    
  * How to remember what a macro tree transducer does?
    
  * Or what are the connections between top-down tree(-to-string) transducers, multi bottom-up tree(-to-string) transducers, tree-walking transducers, (invisible) pebble tree transducers, monadic second-order transductions, unfoldings of rooted directed acyclic graphs (i.e. term graphs) — and what happens when the functions that they compute are composed?
  
  The answers may be found in old papers (mostly coauthored by Engelfriet), but
  maybe you can save some time by first looking at this short note.






§ INTRODUCTION


This relatively short note exists for two reasons.

First, I was frustrated at having to repeat myself in multiple papers involving
tree transducers in some way, such as <cit.>, to justify claims that
follow more-or-less immediately from connecting the dots in the
literature. This is why I wanted to record a bunch of useful facts in
<Ref>. Some parts of that section are also more pedagogical
in purpose.

As for <Ref>, it is meant to spread the word about a
moral rather than technical point, namely the bottom-up
perspective on deterministic macro tree transducers, to dispel the latter's
reputation for being overly complicated. From the reactions I observed at the
Dagstuhl Seminar on Regular Transformations in May 2023 <cit.>, it
seems that many people working on string transducers nowadays find this
perspective enlightening, due to its close proximity to the well-known streaming
string transducer <cit.>. In fact, macro tree transducers are
already presented this way in Courcelle and Engelfriet's
book <cit.>; but I hope that my alternative
exposition will prove helpful for some people. Another point raised is
when is a tree-to-string transducer not quite the same thing as a tree
  transducer that outputs a string?. Finally, <Ref> is a
niche observation about something I found perplexing at first.



§ TOP-DOWN STATES VS BOTTOM-UP REGISTERS





 §.§ Deterministic top-down tree transducers are bottom-up


A top-down tree transducer is like a tree automaton, except that the
result of a transition is not just one state per child of the current node, but
a tree expression involving states applied to children. It can also be seen as a
regular tree grammar controlled by an input tree — just like the derivations of
a grammar, the semantics of a top-down tree transducer can be defined by
rewriting.
[conditional swap, inspired by <cit.>]
  Consider the function
  
    f(a(t,u)) = a(f(u),f(t))      f(t)=t when the root of t is not a

  on trees over the ranked alphabet {a:2,  b:1,  c:0}.

  To compute it, we use the initial state q_0, an auxiliary state q_1 and the transitions:
  
    ⟨ a(t,u)⟩→ a(⟨ u ⟩, ⟨ t ⟩)     ⟨ a(t,u)⟩→ a(⟨ t ⟩, ⟨ u ⟩)     ⟨ b(t) ⟩→ b(⟨ t ⟩)     …

  They are deterministic: each pair of a state and a ranked letter appears only once on the left-hand side of a rule.
  Over the input a(b(c),c), we have the following executions:
  
    ⟨ a(b(c),c) ⟩→ a(⟨ c ⟩, ⟨ b(c) ⟩) → a( ⟨ c ⟩, b(⟨ c ⟩)) →…→ a(c,b(c))


    ⟨ b(a(b(c),c)) ⟩→ b(⟨ a(b(c),c) ⟩) →…→ b(a(b(c),c))

  By determinism, the rewriting relation → always reaches a unique normal form. In this case, t→^* f(t) and t→^* t for any input tree t.




    The bottom-up view.


Another informal way to see a top-down tree transducer is that the states are
mutually recursive procedures. A well-established principle in algorithmics is
that a top-down structurally recursive procedure can be optimized into a
bottom-up dynamic programming algorithm. We can also adopt this point
of view here; as we shall see in later subsections, it brings us closer in
spirit to more recent work on transducers (cf. <ref>).


  The previous example of top-down tree transducer can be seen as a bottom-up
  device whose memory consists of two tree-valued registers
  X_0,X_1. After processing a subtree t, the contents of the register
  X_i is q_it (for i∈{0,1}). The final
    output register X_0 corresponds to the initial state q_0.
  

      
        (top) at (0,1) ;
        (mid) at (0,0) b;
        (bot) at (0,-1) a;
        (b) at (-1,-1.5) b;
        (c) at (1,-1.5) c;
        (cc) at (-1,-2.5) c;
        [-] (top) – node[right]X_0 = X_1 = b(a(b(c),c)) (mid);
        [-] (mid) – node[right]X_0 = a(c,b(c)), X_1 = a(b(c),c) (bot);
        (bot) – (b);
        (bot) – (c);
        (b) – (cc);
      
  





    Beware of nondeterminism.


Let's consider the following nondeterministic rules:

    qb(t)→ a(qt,qt)      qc→ c      qc→ b(c)

By taking the associated rewriting system, we have:

    qb(c)→^* a(c,c) or a(b(c),c) or a(c,b(c)) or a(b(c),b(c))

However, if we work bottom-up, here is what happens. After reading c, the register contains either c or b(c); this is chosen nondeterministically. Then, at the next step, after reading b(c), we get either a(c,c) or a(b(c),b(c)) depending on the earlier choice — but not a(c,b(c)).
Morally, using the terminology of programming languages: top-down nondeterminism is naturally call-by-name, bottom-up nondeterminism is naturally call-by-value (this is related to IO vs OI in automata theory).

From now on, in this article, all automata models under consideration will be deterministic.



 §.§ Top-down lookahead = bottom-up states


Transducers are often extended with a feature called regular
  lookahead, introdu. In general, this notion corresponds in automata theory to being
able to choose a transition based on a regular property of the
future part of the input. Concretely, in the case of top-down tree
transducers <cit.>, the transitions are now of the form

    qa(t_1|r_1,…,t_k|r_k)→some term e.g. b(a(q't_3, c))

where the r_i are some states of an auxiliary deterministic bottom-up tree automaton, called the lookahead automaton. The idea is that this transition can only be applied when the run of the lookahead automaton on the subtree t_i ends in state r_i (for all i). The definition of determinism is adjusted accordingly.

  Suppose we want to replace all subtrees of the input of the form b(t) where
  t does not contain any b by a(t,t). This can be done with a single state q and
  regular lookahead. The lookahead states are r_⊕ if the subtree contains a
  b, and r_⊖ otherwise (this can indeed be implemented by a deterministic
  bottom-up tree automaton). The transitions include:
  
    qb(t|r_⊕)→ b(qt)      qb(t|r_⊖)→ a(qt,qt)


From the bottom-up point of view, this regular lookahead just corresponds to
adding states to the transducer! That is, a configuration of a
corresponding bottom-up device now consists not only of register contents, but
also of a finite control state; but the computation is still performed entirely
bottom-up.
  

      
        (top) at (0,1) ;
        (mid) at (0,0) b;
        (bot) at (0,-1) c;
        [-] (top) – node[right]state = r_⊕,  X = a(c,c) (mid);
        [-] (mid) – node[right]state = r_⊖,  X = c (bot);
      
  


The observations in this subsection and in the previous one are essentially the
meaning of a paper by Fülöp, Kühnemann and Vogler <cit.>:
deterministic top-down tree transducers with regular lookahead =
  deterministic multi bottom-up tree transducers.




 §.§ Top-down tree-to-string transducers — it's not what you think(?)



One of the major results in transducer theory in the 2010s has been the
decidability of equivalence for top-down tree-to-string
  transducers <cit.>, which popularized the Hilbert method
(cf. <cit.>). But what are these devices?



    Strings as unary trees.


We start by presenting a — arguably the — natural way to restrict a
tree transducer model to strings as output. But here, when applied to top-down
tree transducers, it does not give us the right thing. It relies on the
following encoding: strings over the finite alphabet Σ are in canonical
bijection with trees over the ranked alphabet with:

  
  * a unary letter for each letter of Σ;
  
  * a 0-ary letter ε that serves as an end-of-string
        symbol.

For example, the string abac∈{a,b,c}^* becomes the unary tree
a(b(a(c(ε)))).

The tree-to-string functions that can be computed this way by top-down tree
transducers are very weak, since they can only explore one branch of the input
tree. Note, however, that if the input also consists of strings encoded as unary
trees, then we get the very well-studied model of sequential transducers,
see for instance <cit.>.



    The yield operation and concatenable strings.


In fact, in the older literature, it often happens that X
  tree-to-string transducer means ∘ X tree transducer —
and it is the case for X = top-down. The yield of a tree is
the string obtained by reading its leaves from left to right, and erasing some
letters deemed neutral.

Since
(a(t_1,…,t_k)) = (t_1) ·…·(t_k),
this amounts to working with a data type of concatenable strings for the
output. That is, we can describe top-down tree-to-string transducers directly
(without ) using transitions whose right-hand side may use string
concatenation (as in context-free grammars).

  The following single-state top-down tree-to-string transducer computes the
  postfix representation (reverse Polish notation) of its input tree:
  
    qa(t,u)→ qt· qu· a      qb(t)→ qt· b      qc→ c



From the bottom-up point of view, this transducer model should be equivalent to
some counterpart to Fülop et al.'s multi bottom-up tree
transducer <cit.> whose registers contains concatenable strings.
Indeed, the multi bottom-up tree-to-string transducer has been studied
— under this precise name — in Courcelle and Engelfriet's
book <cit.>. As before, top-down regular lookahead
corresponds to bottom-up states.



    The string-to-string case.


It does not make much sense for an automaton to process its input as
concatenable strings. Thus, to get a sensible string-to-string version of
top-down tree-to-string transducers, we should take unary trees as input, but
still use concatenation to produce output strings. The resulting machine model
is a variant of the copyful streaming string transducer <cit.>
— whose memory contains a finite state and concatenable registers — that reads
its input from right to left, instead of left to right.

For other characterizations of this class of string-to-string functions,
see <cit.>.

  Arguably, since concatenation provides the canonical semigroup structure on
  strings, the recognition of a regular language by a semigroup morphism
  processes its input as concatenable strings. An algebraic characterization of
  string-to-string MSO transductions in this vein has been obtained
  in <cit.>. Morally, the fact that both input and output are
  treated as concatenable strings makes it easy to show closure under
  composition.




 §.§ Macro tree transducers store tree contexts



Traditionally, macro tree transducers <cit.> (MTTs) are presented as an extension of top-down tree transducers with parameters, whose rules may look like, for example,

    a(t,u)→t (b(u))   a(t,u)(x) →u(u(x))   c(x) → a(x,x)   …

where  has no parameters and  has the parameter x. A possible run of this MTT is

    a(a(b(c),c),c)→a(b(c),c)(b(c)) →c(c(b(c))) →…

In such a run, something is always applied to an expression that eventually reduces to a tree. But one could also evaluate t(x) for a formal parameter x, for instance:

    a(c,c)(x) →c(c(x)) →c(a(x,x)) → a(a(x,x),a(x,x))

We may therefore say that the value of a(c,c)
is this tree with parameters at some of the leaves, usually called a
tree context. It represents the map x ↦ a(a(x,x),a(x,x)).

Thus, the bottom-up view is as follows: deterministic macro tree
  transducers can be seen as bottom-up devices whose memory consists of
  registers storing tree contexts. This perspective in presented in
Courcelle–Engelfriet <cit.>; it makes the MTT is an
ancestor to later transducer models that are explicitly presented as
manipulating context-valued registers, such as the streaming tree transducer
of <cit.> and the register tree transducer of <cit.>.



    Lookahead elimination.


As in the case of top-down tree(-to-string) transducers, regular lookahead
corresponds to bottom-up states in macro tree transducers. That said, the
significance of the feature differs between these two cases. For deterministic
top-down tree transducers, deciding whether a given transducer with lookahead
computes a function that could be computed without lookahead is still an open
problem, see <cit.> for partial results. For deterministic MTTs,
the answer is always yes:

  For any deterministic MTT with regular lookahead, there is another
  deterministic MTT without lookahead that computes the same function.


To see why this is true, first, it is important to note that MTTs allow states
of arbitrary arities, i.e. with an arbitrary number of parameters. For instance
one may have a ternary state q_2 with a rule such as
q_2b(t)(x_1,x_2,x_3) → a(q_1t(x_3), x_1).
We can then encode the bottom-up lookahead states, ranging over a
finite set R = {r_1,…,r_n}, in the value of an n-ary state, i.e.a bottom-up register storing an n-ary context. The idea — analogous to the
Church encoding of finite sets in λ-calculus — is to represent the
lookahead state r_i by the context (x_1,…,x_n) ↦ x_i.



 §.§ MTTs and string outputs — it is and isn't what you think



Following <Ref>, there are two ways to use macro tree
transducers to output strings.



    Unary trees.


Let us first look into the encoding of output strings as unary trees. The key
remark is that concatenable strings can be represented by contexts, with
concatenation implemented by composition:

    ab · ac = abac   ⇝   (x↦ a(b(x))) ∘ (x↦ a(c(x))) = (x↦ a(b(a(c(x)))))

Conversely, over a ranked alphabet of unary letters plus an end-of-string marker
ε, any context with n parameters x_1,…,x_n must have the
form

    a_1(a_2(… (a_n_can be represented by the string a_1… a_n(either x_i for some i∈{1,…,n} or ε_finite data)) … ))

Therefore, we have:

  Macro tree transducers with unary trees as output are equivalent in expressive
  power to top-down tree-to-string transducers with regular lookahead.

According to the end of <Ref>, this means that macro tree
transducers whose inputs and outputs both consist of unary trees are the same as
right-to-left copyful streaming string transducers (SSTs). Note that states can
be eliminated in copyful SSTs <cit.>, but for reasons
that crucially depend on the input being a string; these reasons are unrelated
to the elimination of lookaheads in MTTs sketched earlier.


  Right-to-left copyless SSTs <cit.> would then correspond to
  strongly single-use MTTs <cit.> with regular lookahead whose
  inputs and outputs are unary trees, with a subtlety: in MTTs, the output is
  taken to be the final value of some fixed state/register, whereas in SSTs, the
  output depends on the final register values in a less restrictive way. This
  makes a difference as the function below can be computed by a right-to-left
  copyless SST (exercise for the reader), but not by a strongly single-use
  MTT <cit.>:
  
    a^n↦ a^n     a^nbw ↦ a^nbb^|w| for w ∈{a,b}^*





    Yield.


Post-composing MTTs with the  operation results in the so-called
macro tree-to-string transducers, which manipulate string
  contexts such as (x_1,x_2) ↦ x_2 ab x_1 ac x_2 b. Morally,
these transducers are to macro grammars <cit.> what top-down
tree-to-string transducers are to context-free grammars; this is where the name
comes from. Several equivalent characterizations of macro tree-to-string
transducers may be found in <cit.>. We shall discuss
them further in <Ref>.






§ RELATIONSHIPS BETWEEN DETERMINISTIC TRANSDUCTION CLASSES





 §.§ Monadic second-order transductions with sharing / unfolding



Monadic Second-Order logic (MSO) is a logic over relational structures
(sets endowed with relations). For instance one can encode a string w as a
relational structure by taking its set of positions {1,…,|w|} endowed
with the total order ⩽ and, for each letter a, a unary relation
a(i) = the i-th letter is a. Over strings (resp. trees), the
properties that MSO can define correspond exactly to the regular languages
(resp. regular tree languages). Thus, MSO provides a canonical generalisation
of regular languages to structures beyond strings and trees; typically, graphs,
as discussed in Courcelle and Engelfriet's book <cit.>.

MSO transductions, also covered in <cit.>, are the usual
way to define transformations of relational structures using MSO. (One may also
consider MSO interpretations <cit.> or MSO set
interpretations <cit.> but they are not always as well-behaved,
especially over structures other than strings and trees.) String-to-string MSO
transductions are also called regular functions and have a rich theory,
see the survey <cit.>. Tree-to-tree MSO transductions are also
well-studied, with several equivalent characterizations by machine
models <cit.>. For instance a major theorem of
Engelfriet and Maneth <cit.> is that the tree-to-tree functions
definable by MSO transductions are exactly those computed by macro tree
transducers of linear growth, i.e. output size = O(input
  size); see <Ref> for a generalisation. Thus, most examples of
tree-to-tree functions seen in the previous section are MSO transductions.

However, one can easily define top-down tree transducers with non-linear growth:

  The following transducer
  
    S(t)→ a(t,t)     0→ c     S(t)→ b(t)     0→ b(c)

  computes the function
  S^n(0) ↦ a(b^n(c),a(b^n-1(c), … a(b(c),c)…)) with quadratic
  growth.


The thing to note about this example is that the output contains many repeated
subtrees. For instance, for S(S(0)) ↦ a(b(b(c)),a(b(c),c)), the
subtree b(c) is repeated twice; and this is because in the computation,
0 appears at two different places. One may compress the output
tree into a shared representation — a rooted directed acyclic
  graph (DAG) — where all copies of each subtree produced by the same
qt are merged together:


  
    (a) at (0,0) S;
    (b) at (0,-1) S;
    (c) at (0,-2) 0;
    (a) – (b);
    (b) – (c);

    at (1,-1) ↦;

    (a') at (3,0) a;
    (a”) at (2,-0.4) b;
    (b') at (4,-1) a;
    (b”) at (3,-1.4) b;
    (c') at (4,-2) c;
    [->] (a') – (a”);
    [->] (a') – (b');
    [->] (b') – (b”);
    [->] (a”) – (b”);
    [->] (b') – (c');
    [->] (b”) – (c');

    at (5,-1) ↦;

    (a') at (7,0) a;
    (a”) at (6,-0.4) b;
    (b') at (8,-1) a;
    (b”) at (7,-1.4) b;
    (bb) at (6,-1.4) b;
    (c') at (8,-2) c;
    (c”) at (7,-2) c;
    (cc) at (6,-2) c;
    (a') – (a”);
    (a') – (b');
    (b') – (b”);
    (a”) – (bb);
    (bb) – (cc);
    (b') – (c');
    (b”) – (c”);
  


(Here we have also merged the two c leaves from 0 and 0.)

In this factorisation, the first tree-to-DAG map is definable as an MSO
transduction. The second operation, that recovers an output tree from a DAG, is
called unfolding. In general, all functions computed by top-down tree
transducers belong in the function class

    ∘ (MSO tree-to-DAG transductions)
 which is called
MSO transductions with sharing (MSOTS) in <cit.> — we use this
name here — and MSO term graph transductions
in <cit.>.



 §.§ Attributed vs tree-walking transducers vs MSOTS


Let us discuss characterisations of MSOTS by machines. There is a recent one
based on transducers using almost linear λ-terms
in <cit.>. A more classical one relies on
attributed tree transducers (ATTs) — which come from Knuth's attribute
grammars <cit.> — and on MSO relabelings, i.e. MSO tree
transductions that keep the structure of the tree intact, and merely change the
label of each node.


  ATT∘MSO relabeling = MSOTS.

(When we write this kind of equality, both sides of = are understood to refer to function classes, and thus the equality denotes an equivalence in expressive power.)

As explained in <cit.>, the ATT and the
deterministic tree-walking transducer (TWT) – which appears under a
different name in <cit.>, cf. <Ref> – are
essentially notational variations of the same formalism
(quoting <cit.>). Tree-walking transducers are like
top-down tree transducers, except that transitions do not always go
downwards in the input tree: qsome node v in
    the input may be rewritten into an expression that contains
q'the parent node of v. Arguably, TWTs are the natural
generalisation to trees of two-way transducers on strings.

The correspondence between the ATT and the TWT relates the former's
attributes to the latter's states, in an analogous fashion
to the bottom-up registers / top-down states correspondence of
<Ref>. There are subtleties related to noncircularity
which make the ATT slightly weaker, but they become irrelevant in presence of
preprocessing by MSO relabeling.

  In <cit.>, TWTs are called 0-pebble tree
    transducers, as the case k=0 of the k-pebble tree transducers
  introduced in <cit.> (the latter have seen a resurgence in recent years
  in the study of string-to-string polyregular functions <cit.>). The
  terminology tree-walking was only later used to speak of 0-pebble
  transducers, starting with <cit.>, but it was already in use for
  the tree-to-string version of these devices since the late 1960s <cit.>
  — there, the output strings are produced as if they were unary trees. Let us
  also mention the RT(Tree-walk) transducers
  of <cit.> from the 1980s, discussed
  in <cit.>.


When a TWT takes as input a tree that has been preprocessed by an MSO
relabeling, it has access to some extra information on each node; this finite
information recorded by the relabeling is necessarily a regular property of the
input tree with this node distinguished. Equivalently, one could replace the
preprocessing by adding to the TWT the ability to query on the fly the
relevant regular properties of the current node. This feature is usually called
regular lookaround or MSO tests, see e.g. the introduction
to <cit.>. Hence:

    MSOTS = TWT∘MSO relabeling = TWT with regular lookaround a.k.a. MSO tests

However, in the absence of regular lookaround, TWTs are much weaker, since:

  Nondeterministic tree-walking automata do not recognise all regular tree
  languages <cit.>, and deterministic TWA are even
  weaker <cit.>.


Finally, one can impose a single use restriction on both attributed
and (deterministic) tree-walking transducers to avoid sharing phenomena, leading
to characterisations of tree-to-tree MSO transductions (MSOT):

    MSOT   = single-use ATT∘MSO relabeling <cit.>
       = single-use TWT with MSO tests (regular lookaround) <cit.>





 §.§ Composition hierarchies: MSOTS (& invisible pebbles / Caucal hierarchy) vs MTT (& iterated pushdowns / safe higher-order)


Engelfriet, Hoogeboom and Samwel have characterised the composition of
two deterministic tree-walking transducers with MSO tests using a machine
model: the invisible pebble tree transducer
(IPTT) <cit.>, a variant of the k-pebble tree transducer of
<Ref>. According to the previous subsection, we may equivalently
state their result as:

  ^2def.=∘ = IPTT.


The invisible pebble tree transducer manipulates an unbounded stack of
pebbles, which are pointers to nodes of the input tree. Similarly, the
memory of the pushdown tree transducer <cit.>
consists mainly of a stack of pointers to input nodes; the difference is that
the reading head of an IPTT moves like that of a TWT, whereas the pointers in a
pushdown tree transducers can only move top-down. This suggests that
MTT⊂IPTT which is indeed
true <cit.>.

In fact, we may also look at the composition of k MSOTS beyond the case k>2,
as well as the composition of several MTTs. It turns out that the two
hierarchies are interleaved:

  ∀ k⩾1, ^k⊂^k⊂^k+1.

  In particular, ⋃_k⩾1^k = ⋃_k⩾1^k.


  This is beause:
  
    
  * MTT = MSOTS∘top-down tree transducer <cit.>;
    
  * MSOTS = top-down tree transducer∘MSOTS <cit.>.
  
  (beware: the order of composition is reversed compared to the usual in <cit.>).


Let us mention that the main theorem of the above-cited paper <cit.> is:

  The functions (cf. <ref>) in the ^k
  hierarchy (equivalently, in the ^k hierarchy) of linear
    growth are exactly the tree-to-tree MSO transductions.


Engelfriet and Vogler have shown that the class MTT^k (for some fixed
k⩾1) corresponds to the expressive power of the iterated
  pushdown tree transducer <cit.>,
which generalizes the aforementioned pushdown tree transducer by working with a
stack of … of stacks of input pointers, with nesting depth k. (See also the
work of Sénizergues on string-to-string
functions <cit.>.) Also, it seems natural to believe
that:

  MSOTS^k+1 = a variant of iterated pushdown transducers whose
  input pointers can move in a tree-walking rather than top-down fashion, with
  nesting depth k, such that the case k=1 corresponds to the IPTT.

[Idea]
  I expect this to be derivable from the
  aforementioned <cit.>, plus the general
  result <cit.> about adding a pushdown
  layer on top of a storage type (see
  also <cit.>), but I'm too lazy to spell out and
  check the details.


The class MTT^k can also be characterised by the high level
  tree transducer <cit.>, which stores some kind of
higher-order functions: the tree contexts in MTTs are first-order i.e.tree-to-tree functions, second-order functions map first-order functions to
trees, etc.



    Connections with higher-order recursion schemes.


Engelfriet and Vogler's high level tree transducer is directly inspired by
Damm's high level grammars <cit.>. As explained for instance
in <cit.>, high level grammars are very close
syntactically — and equivalently expressive — to safe higher-order
grammars. This notion of safety was introduced by Knapik, Niwiński and
Urzyczyn <cit.> in the context of higher-order recursion
  schemes; a recursion scheme is a grammar-like specification of a single
infinite tree. Safe recursion schemes of order k describe exactly the same
infinite trees as iterated (a.k.a. higher-order) pushdown tree-generating
automata of nesting depth k <cit.> — a result
that is strikingly similar to the equivalence between MTT^k and
k-iterated pushdown transducers.

Moreover, the same class of infinite trees (for a fixed k⩾0) can be
equivalently described as those obtained by applying a function in
(∘tree-to-graph MSO transduction)^k+1 to a finite tree
— this is the Caucal hierarchy <cit.>. Here the
output of the MSO transductions are rooted directed graphs that are not
necessarily acyclic, and the unfolding operation is generalized to generate
infinite trees when the input has cycles. Since an MSOTS is defined as
∘tree-to-DAG MSOT, the Caucal hierarchy is clearly
analogous to the MSOTS^k+1 tree transducer hierarchy.

This means that the counterpart to the strict inclusion
MTT^k⊂MSOTS^k+1 in the setting of recursion schemes
is an equality. <Ref> suggests a heuristic explanation: since
iterated pushdown tree-generating automata do not have an input, the difference
between top-down pointers and tree-walking pointers to the input disappears.



 §.§ The MTT composition hierarchy for tree-to-string functions



For a class of tree-to-tree functions , let () be the subclass of functions that output strings encoded as unary trees. Recall from <Ref> the definition of the yield operation and of the top-down tree-to-string transducer. In that section we explained that

    (^1) = top-down tree-to-string transducer        (<Ref>)

For the next levels of the MTT^k hierarchy, we also have:

  ∀ k ⩾ 1, (^k+1) = ∘^k.


The case k=1 tells us that (^2) = macro tree-to-string transducer (cf. <ref>).

  This is established in <cit.> using high level
    tree transducers, but it can also be shown by working directly on
  compositions of MTTs:
  
    (^k+1)    = (^1)∘^1∘^k-1
       = ∘(top-down tree transducer) ∘_= , cf. <cit.>∘ ^k-1

  (beware: again, in <cit.>, the notation ∘ is flipped compared to ours).


Thanks to this, for instance, Engelfriet and Maneth's bridge
  theorem <cit.> on output languages, originally stated
using , can now be seen as relating (^k) and
(^k+1) for each k⩾1. This rephrasing has proved useful in
the recent work <cit.>.



