The Complexity of Tree Transducer Output Languages
Kazuhiro Inaba1 and Sebastian Maneth2,3
1
2

The University of Tokyo, kinaba@is.s.u-tokyo.ac.jp
National ICT Australia, sebastian.maneth@nicta.com.au
3
University of New South Wales, Sydney

Abstract. Two complexity results are shown for the output languages generated by compositions of macro
tree transducers. They are in NSPACE(n) and hence are context-sensitive, and the class is NP-complete.

1

Introduction

Macro tree transducers (mtts) [12, 14] are a finite-state machine model of tree-to-tree translations. They
are motivated by syntax-directed semantics of programming languages and recently have been applied to
XML transformations and query languages [18, 21]. Mtts are a combination of top-down tree transducers [22, 24] and macro grammars [13]. They process the input tree top-down while accumulating several
output trees using their context parameters. Sequential composition of mtts gives rise to a powerful hierarchy (the “mtt-hierarchy”) of tree translations which contains most known classes of tree translations
such as those realized by attribute grammars, by MSO-definable tree translations [5], or by pebble treetransducers [20]. Consider the range, or output language, of a tree translation; it is a set of trees. If weapply “yield” to these trees, i.e., concatenate their leaf symbols from left to right, we obtain a string language. The string languages obtained in this way from the mtt-hierarchy form a large class (containing
for instance the IO- and OI-hierarchies [6]) with good properties, such as being a full AFL and having
decidable membership, emptiness, and finiteness [7].
In this paper we study the complexity of the output (string or tree) languages of the mtt-hierarchy.
Note that we do not explicitly distinguish between string or tree output languages here, because thetranslation “yield” which turns a tree into its frontier string (seen as a monadic tree) is a particular simple macro tree translation itself and hence the corresponding classes have the same complexity. Small
subclasses of our class of languages considered here are the IO-macro languages (or, equivalently, theyields of context-free-tree languages under IO-derivation) and the string languages generated by attributegrammars. Both of these classes are LOG(CFL)-complete by [2] and [10], respectively. Another subclassof our class is that of OI-macro languages, which are equivalent to the indexed languages [1], by [13].
This class is known to be NP-complete [23]. Hence, our class is NP-hard too (even already at level2). Our first main result is that output languages of the mtt-hierarchy are NP-complete; thus, the complexity remains in NP when going from indexed languages to the full mtt-hierarchy. In terms of spacecomplexity, languages generated by compositions of top-down tree transducers (mtts without context
parameters) are known to be in DSPACE(n) [3]. This result was generalized in [17] to compositions of
total deterministic mtts. Our second main result is that output languages of the mtt-hierarchy (generated
by compositions of nondeterministic mtts) with regular tree languages as inputs are in NSPACE(n) andthus are context-sensitive. The approach of our proof can be seen as a generalization of the proofs in [3]and [17]; moreover, we make essential use of the idea of compressed representation of backtracking
information, used by Aho in [1] for showing that the indexed languages are in NSPACE(n).
We first solve the “translation membership” problem for a single mtt M . That is, we show that, given
trees s and t, we can determine whether or not the pair (s, t) is in M ’s translation, in linear space andpolynomial time with respect to |s| + |t| on a nondeterministic Turing Machine (|s| denotes the sizeof the tree s). The challenge here is the space complexity; we use a compressed representation of M ’s
output trees for input s, inspired by [19], and then check if t is contained using a recursive procedurein which nodes needed for backtracking are compressed using a trie, similar to Aho’s compression ofindex strings in [1]. Then, we generalize these results from one mtt to compositions of mtts. Here, thechallenge is the existence of intermediate trees. Consider the composition τ of two translations realized
by mtts: τ1 followed by τ2 . To check (s, t) ∈ τ , we nondeterministically guess an intermediate tree u,and check whether (s, u) ∈ τ1 and (u, t) ∈ τ2 . From the complexity result of single mtts, we knowthat this can be done in O(|s| + |u| + |t|) space. This can, however, be much larger than O(|s| + |t|);the size |u| of the intermediate tree u can actually be double-exponentially larger than |s| and |t|. The
basic idea to prove the linear size complexity for compositions of mtts is to bound the sizes of all suchintermediate input trees. This is achieved by putting the mtts in certain normal forms such that they do
not delete much of their input, in the sense that every output tree t has a corresponding input tree of size
only linearly larger than |t|. In fact, also the initial input tree s can be changed into a smaller tree s′ ofsize linear in |t|, for which τ (s′ ) = τ (s). Limiting the size of intermediate trees can also be used forshowing the time complexity NP. We nondeterministically guess all linear size intermediate trees, andtest the translation membership of each single mtt in polynomial time.
Although the idea of bounding the size of intermediate trees is quite similar to [3] and [17], theexistence of context parameters and nondeterminism together adds some difficulty in every step of theproof. For example, consider the mtt Mdexp with the following three rules r0 , r1 , and r2 :⟨q0 , a(x)⟩ → ⟨q, x⟩(⟨q, x⟩(e))(r0 )⟨q, a(x)⟩(y) → ⟨q, x⟩(⟨q, x⟩(y))(r1 )⟨q, e⟩(y) → +(b(y, y), c(y, y))(r2 )Here, + denotes a nondeterministic choice; e.g., when the state q reads an input node labeled e, it
generates an output node labeled either b or c. This mtt takes a tree of form a(a(· · · a(e) · · · )) as input(with n occurrences of a) and generates a full binary tree of height 2n (note that, without parameters, theheight growth can only be linear) with each non-leaf node arbitrarily labeled either b or c. Therefore,
2nthe size of the set of possible output trees is 22 . To decide whether (s, t) ∈ τMdexp for given trees sand t, we essentially have to find the correct choice among the triple exponentially many candidates. To
address the issue, we (1) instead of solving the membership problem for all mtts, only deal with mtts inthe above mentioned non-deleting normal form, and which are linear with respect to the input variables,and (2) exploit the compressed representation of outputs of mtts [19] for manipulating the output set.
Note that due to nondeterminism we cannot anymore obtain some of the useful normal forms (nonerasing, which is similar to having no ϵ-moves in a string transducer, and non-parameter-deleting) usedin [17] for total deterministic mtts. We address this issue by introducing a slight extension of mtts,
namely, mtts with choice and failure, which re-enable us to have the non-erasing normal form, andcompensate the absence of the non-parameter-deleting normal form.

2 Preliminaries
We denote by ϵ the empty list, i.e., a list of length 0, and by l1 .l2 the concatenation of two lists l1 andl2 . A list l is said to be a prefix of a list l′ if there is a list l′′ such that l.l′′ = l′ , and to be a proper
prefix if l′′ ̸= ϵ. For a finite set A, we denote by |A| the number of its elements. A finite set Σ with amapping rank : Σ → N is called a ranked alphabet. We often write σ (k) to indicate that rank(σ) = k
and write Σ (k) to denote the subset of Σ of rank-k symbols. The product of Σ and a set B is the ranked
alphabet Σ ×B = {⟨σ, b⟩(k) | σ (k) ∈ Σ, b ∈ B}. Throughout the paper, we fix the sets of input variables
X = {x1 , x2 , . . . } and parameters Y = {y1 , y2 , . . . } which are all of rank 0, and the set of choice nodes
C = {θ(0) , +(2) }. We assume any other alphabet to be disjoint with X, Y , and C. The set Xi is definedk
as {x1 , . . . , xi }, and Yi is defined similarly.
z }| {The set TΣ of trees t over a ranked alphabet Σ is defined by the BNF t ::= σ(t, . . . , t) for σ ∈(k)Σ . Instead of σ() we usually write σ. We recursively define the function labelΣ from TΣ × N∗ to2

Σ as follows. For t = σ(t1 , . . . , tk ), σ (k) ∈ Σ, k ≥ 0, and t1 , . . . , tk ∈ TΣ , labelΣ (t, ϵ) = σ andlabelΣ (t, i.ν) = labelΣ (ti , ν). Thus, the empty list ϵ denotes the root node and ν.i denotes the i-thchild of ν. We omit the subscript Σ if clear from the context. We define the set pos(t) = {ν ∈ N∗ |label(t, ν) is defined}. For p ∈ pos(t), t|ν denotes the subtree of t rooted at the node ν. We write |t|
as a shorthand for |pos(t)|. A subset L ⊆ TΣ is called a tree language. By REGT, we denote the classof regular tree languages [15]. Let Σ and ∆ be ranked alphabets. A relation τ ⊆ TΣ × T∆ is called atree translation (over Σ and ∆) or simply a translation. For two translations τ1 and τ2 , their sequential
composition τ1 ; τ2 (“τ1 followed by τ2 ”) is the translation {(x, z) | ∃y((x, y) ∈ τ1 , (y, z) ∈ τ2 )}. For
two classes T1 and T2 of translations, we define T1 ; T2 = {τ1 ; τ2 | τ1 ∈ T1 , τ2 ∈ T2 }. The k-foldkcomposition
S of the class T of translations is denoted by T . For a tree language L and a translation τ ,τ (L) = {τ (t) | t ∈ L}.For a class F of languages and a class T of translations, we denote by T (F )the class of output languages {τ (L) | τ ∈ T, L ∈ F }.
A macro tree transducer (mtt) M is a tuple (Q, Σ, ∆, q0 , R), where Q is the ranked alphabet ofstates, Σ and ∆ are the input and output alphabets, q0 ∈ Q(0) is the initial state, and R is the finite setof rules of the form ⟨q, σ(x1 , . . . , xk )⟩(y1 , . . . , ym ) → r where q ∈ Q(m) , σ ∈ Σ (k) , and r is a tree inT∆∪(Q×Xk )∪Ym . Rules of such form are called ⟨q, σ⟩-rules, and the set of right-hand sides of all ⟨q, σ⟩rules is denoted by Rq,σ . We always assume Σ (0) and ∆(0) (and thus, TΣ and T∆ ) are non-empty. The
rules of M are used as term rewriting rules in the usual way. We denote by ⇒M the derivation relationof M on T(Q×TΣ )∪∆ , and by u↓M the set {t ∈ T∆ | u ⇒∗M t}. Note that “state-calls” ⟨q, xi ⟩ can benested and therefore different orders of evaluation yield different trees. Unless otherwise specified, we
assume the outside-in (OI) derivation in which we always rewrite the outermost (= top-most) state calls.
By Corollary 3.13 of [12], this order of evaluation yields the same set of output trees as the unrestricted
order, i.e., the case where no restriction is imposed on the order of evaluation. The translation realized
by M is the relation τM = {(s, t) ∈ TΣ × T∆ | t ∈ ⟨q0 , s⟩↓M }. We omit the subscript M if it is clear
from the context. We denote by MT the class of translations realized by mtts. An mtt is called a top-downtree transducer (tt) if all its states are of rank 0; the corresponding class of translations is denoted by T.
We call an mtt deterministic (total, respectively) if for every ⟨q, σ⟩ ∈ Q × Σ, the number |Rq,σ | of rules
is at most (at least) one; the corresponding classes of translations are denoted by prefix D (t ). An mtt islinear (denoted by prefix L) if in every right-hand side of its rules each input variable xi ∈ X occurs at
most once. The same notation is used for tts; for instance, Dt T denotes the class of translations realized
by total deterministic tts.
Macro Tree Transducers with Choice and Failure For a technical reason, we define a slight
extension of mtts. An mtt with choice and failure (mttcf ) M is a tuple (Q, Σ, ∆, q0 , R) defined as
for normal mtts, except that the right-hand sides of rules are trees in T∆∪(Q×Xk )∪Ym ∪C (recall thatC = {θ(0) , +(2) }). The derivation relations (⇒M and ↓M ) and the realized translation (τM ) are definedsimilarly as for mtts, with two additional rewrite rules: +(t1 , t2 ) ⇒M t1 and +(t1 , t2 ) ⇒M t2 . Thus, +denotes nondeterministic choice and θ denotes failure (because there is no rule for it). Again, we assume
the outside-in evaluation order. For a right-hand side r of an mttcf, we say a position ν ∈ pos(r) is
top-level if for all proper prefixes ν ′ of ν, label(r, ν ′ ) ∈ ∆ ∪ C. We say an mttcf is canonical if for every
right-hand side r and for every top-level position ν ∈ pos(r), label(r, ν) ∈/ C.
The idea of the choice and failure nodes comes from [12]; there they show that MT = Dt MT ; SET,
where SET is the class of translations set∆ : T∆∪C → T∆ with set∆ (θ) = ∅, set∆ (+(c1 , c2 )) =set(c1 ) ∪ set(c2 ), and set∆ (δ(c1 , . . . , ck )) = {δ(t1 , . . . , tk ) | ti ∈ set∆ (ci )} for δ ∈ ∆. Let us
briefly summarize the proof. For any mttcf (or mtt) M , we can always construct a total deterministic mttcf M ′ that realizes the same translation, by taking the ⟨q, σ⟩-rule of M ′ as ⟨q, σ(· · · )⟩(· · · ) →+(r1 , +(r2 , . . . , +(rn , θ) · · · )) where {r1 , . . . , rn } = Rq,σ . Also note that the mttcf M ′ = (Q, Σ, ∆,q0 , R′ ) can be regarded as the mtt M ′′ = (Q, Σ, ∆ ∪ C, q0 , R′ ), by merely interpreting the θ and +nodes as output symbols. Each output of M ′′ is a “choice tree” denoting the set of possible output3trees. Obviously, the translation set∆ carries out this interpretation of choice trees, and thus we have
τM = τM ′′ ; set∆ .
The reason why we introduce mttcfs is twofold. One reason is the decomposition result explained
above, through which we give the complexity bound of a single mtt translation in Section 3. The otherreason is its more flexible use of nondeterminism and partiality. Suppose an mttcf rule ⟨q, σ(x1 )⟩(y1 ) →⟨p, x1 ⟩(+(δ1 , δ2 )). This could produce more output than an mtt with the pair of rules ⟨q, σ(x1 )⟩(y1 ) →⟨p, x1 ⟩(δ1 ) and ⟨q, σ(x1 )⟩(y1 ) → ⟨p, x1 ⟩(δ2 ), because the state p may copy its parameter. Although infact we can still emulate + and θ by introducing auxiliary states, it seems much simpler to use + and θ.
For example, mttcfs have simple normal forms, such as non-erasure (Section 4.1), while the emulating
mtts do not have such a normal form.

3 Complexity of a Single MTT
In this section we show that for any canonical mttcf M having properties called path-linear and nonerasing, there is a nondeterministic Turing Machine that decides whether a given pair (s, t) of trees is in
τM in O(|s| + |t|) space and in polynomial time with respect to |s| + |t|. Thus, this “translation membership” problem is in NSPACE(n) and NP. Two previous works on the same membership problem for
restricted classes of macro tree transducers – for total deterministic mtts [17] and for nondeterministic mtts without parameters (top-down tree transducers) [3] – both give DSPACE(n) algorithms. First
let us briefly explain where the difficulty arises in our case, i.e., with nondeterminism and parameters.
For total deterministic mtts, the DSPACE(n) complexity is proved via a reduction to the case of linear total deterministic mtts, and then to attribute grammars (which are deterministic by default), whose
output languages are LOG(CFL)-complete and therefore have DSPACE(log(n)2 ) membership test [10].
For nondeterministic tts, the complexity is achieved by a straightforward backtracking-based algorithm;
given the input tree s and the output tree t, it generates each possible output of s by simulating the recursive execution of state calls, while comparing with t. The following two facts imply the DSPACE(n)complexity: (1) the depth of the recursion is at most the height of s, and (2) to backtrack we only need toremember for each state call the rule that was applied (which requires constant space). Note that neither(1) nor (2) hold for mtts; the recursion depth can be exponential and the actual parameters passed to eachstate call must also be remembered for backtracking.
Here we concentrate on a restricted class of mttcfs, namely, canonical, non-erasing, and path-linear
mttcfs, which is exactly the class of mttcfs needed later in Section 4, to obtain the complexity result forthe output languages of the mtt-hierarchy. For a canonical mtt, we define a right-hand side of a rule tobe non-erasing if it is not in Y . A canonical mttcf is non-erasing if the right-hand sides of all its rules
are non-erasing. An mttcf is path-linear if a subtree of the form ⟨q, xi ⟩(· · · ⟨p, xj ⟩(· · · ) · · · ) in its rules
implies i ̸= j.
Making MTTCFs Total Deterministic Let M be a canonical, non-erasing, and path-linear mttcf.
It is easy to see that As noted in Section 2, we can always construct a total deterministic mttcf M ′equivalent to M by simply taking ⟨q, σ(· · · )⟩(· · · ) → +(r1 , · · · , +(rn , θ) · · · ) for {r1 , . . . , rn } = Rq,σ .
Then, M ′ = (Q, Σ, ∆, q0 , R′ ) can be seen as a total deterministic mtt N = (Q, Σ, ∆ ∪ C, q0 , R′ ) whose
outputs are the choice trees denoting sets of output trees of M . The canonicity and the non-erasure of
M implies that in any right-hand side r ∈ R′ and every position ν ∈ pos(r) with label(ν) ∈ Y , there
exists a proper prefix ν ′ of ν with label(ν ′ ) ̸= +. Path-linearity is preserved from M to M ′ .
Compressed Representation Our approach is to represent the output choice tree τN (s) in a compact (linear size) structure, and then compare it to the given output tree t. Given a total deterministic mtt
N and an input tree s ∈ TΣ , we can, in time O(|s|), calculate a straight-line context-free tree grammar(or SLG, a context-free tree grammar that has no recursion and generates exactly one output) of size
O(|s|) that generates τN (s), using the idea of [19]. Rather than repeating the full construction of [19],we here give a direct representation of the nodes of τN (s).
4Let N be a total, deterministic, non-erasing, and path-linear mtt with output alphabet ∆ ∪ C andlet s be an input tree. Let E = {(r, ν) | q ∈ Q, σ ∈ Σ, r ∈ Rq,σ , ν ∈ pos(r)}. For a list e =(r0 , ν0 ) . . . (rn , νn ) of elements of E, we define orig(e) (the origin of e) as ϵ.i0 . . . ik−1 where k is thesmallest index satisfying label(rk , νk ) ∈/ Q × X (or, let k = n + 1 when all labels are in Q × X) and ij isthe number such that ⟨q, xij ⟩ = label(rj , νj ) for some q. We call e well-formed if label(ri , νi ) ∈ Q × X
for every i < n, label(rn , νn ) ∈ ∆ ∪ C, and orig(e) ∈ pos(s). Intuitively, e is a partial derivation ora “call stack” of the mtt N . Each node of τN (s) can be represented by a well-formed list, which canbe stored in O(|s|) space because its length is at most 1 + (height of s) and the size of each element
depends only on the size of the fixed mtt, not on |s|. Note that e can represent many nodes in τN (s) if
the mtt is non-linear in the parameters. For instance, for Mdexp from the Introduction and the input trees3 = a(a(a(e))), the list (r0 , ϵ.1)(r1 , ϵ.1)(r1 , ϵ.1)(r2 , ϵ.1) represents all b-nodes at depth 16 of the treeτMdexp (s3 ), of which there are 28 many. The label c-label(e) of the node represented by e is label(rn , νn ).
The operation c-child(e, i) which calculates the representation of the i-th child of the node represented
by e is defined in terms of the following three operations. For a well-formed list e = (r0 , ν0 ) . . . (rn , νn )with rank(c-label(e)) = m, we define downi (e) for 1 ≤ i ≤ m as (r0 , ν0 ) . . . (rn , νn .i). For e =(r0 , ν0 ) . . . (rn , νn ) such that label(rn , νn ) = yi ∈ Y , we define pop(e) = (r0 , ν0 ) . . . (rn−1 , νn−1 .i).
For a list e = (r0 , ν0 ) . . . (rn , νn ) where label(rn , νn ) = ⟨q, xj ⟩ ∈ Q × X, we define expand(e) =(r0 , ν0 ) . . . (rn , νn )(rn+1 , ϵ) where rn+1 is the right-hand side of the unique ⟨q, label(s, orig(e))⟩-rule.
Then, the operation c-child(e, i) is realized by the following algorithm: first apply downi to e, thenrepeatedly apply pop as long as possible, and then repeatedly apply expand as long as possible. The nonerasure of N ensures that this yields a well-formed list; in the last step, when expand cannot be applied
to e = . . . (rn , νn ), label(rn , νn ) is obviously not in Q × X and by non-erasure is not in Y , hence it isin ∆ ∪ C. Since the length of a well-formed list is bounded by |s| and pop (and expand, respectively)
always decreases (increases) the length of the list by one, each of them are executed at most |s| times
in the calculation of c-child. Hence, c-child runs in polynomial time with respect to |s|. Similarly, therepresentation of the root of τN (s) is obtained in polynomial time by repeatedly applying expand aslong as possible to e0 = (r0 , ϵ) where r0 denotes the right-hand side of the unique ⟨q0 , label(s, ϵ)⟩-rule.
Note that a similar list representation is used in the proof of Theorem 3 in [4].
Matching Algorithm with NP Time Complexity
Let t ∈ T∆ . Figure 1 shows the nondeterministic algorithm MATCH that decides, given a well-formed list e
MATCH (e, v)
and a node v of t, whether the set of trees represented by
1: while label(e) = + do2:e ← c-child(e, k) where k = 1 or 2,
the choice tree at e contains the subtree of t rooted at v.
nondeterministically chosen
The operations c-label and c-child are defined as above.
3: if c-label(e) ̸= label(v) then4:
return false
The operations label, rank, and child are basic tree op5: else if rank(label(v)) = 0 thenerations, assumed to run in polynomial time with respect
6:
return true
to |t|. If we apply MATCH to the representations of the
7: else8:
for i = 1 to rank(label(v)) doroot nodes of τN (s) and v = ϵ, we can decide whether
9:
if not MATCH(c-child(e, i), child(v, i)) then(s, t) ∈ τM . Since this is the standard top-down recursive
10:
return false
11:
return truecomparison of two trees, the correctness of the algorithm
should be clear.
Fig. 1. Matching Algorithm
In each nondeterministic computation, MATCH iscalled once for each node of t. In each call, the whileloop iterates at most c|s| times for a constant c. This isdue to non-erasure, i.e., for every Y -node in right-hand sides there exists a non-+ ancestor node. If
we once expand a list for obtaining c-child, we never see Y -nodes in right-hand sides (thus never pop)
before seeing some ∆-node. Thus, during the while-loop, the sequence of applied operations must be:
first pop’s and down’s are applied, and then expand is applied (if any), and after that no pop is applied,i.e., the only operations applied are expand or down. In other words, it has to be in the regular set
5

(pop|down)∗ (expand|down)∗ . However, since the length of a well-formed list is at most |s|, we can continuously pop without expanding at most |s| times, and the same for expand without popping. Also, thenumbers of continuous down’s are bounded by the height of the right-hand sides of the rules of N . Thus,
the loop terminates after at most 2 · (1 + the maximum height of right-hand sides of N ) · |s| iterations.
Altogether, the total running time is polynomial in |s| + |t|.
Linear Space Complexity The MATCH algorithm takes O((|s| + log |t|)|t|) space if naively implemented, because in the worst case the depth of recursion is O(|t|) and we have to remember e (whichcosts O(|s|) space) and v (O(log(|t|)) space at least, depending on the tree node representation) in eachstep of the recursion. However, note that the lists of nodes share common prefixes! Suppose the root
node is represented by (r0 , ν0 )(r1 , ν1 )(r2 , ν2 )(r3 , ν3 ) and its child node is obtained by applying down1 ,pop, and expand. Then the child node is of the form (r0 , ν0 )(r1 , ν1 )(r2 , ν2′ )(r3′ , ν3′ ), which shares thefirst two elements with the root node representation. We show that if we store lists of nodes with common prefixes maximally shared, then, in the case of path-linear mtts, their space consumption becomesO(|s| + |t|). The idea of sharing lists resembles the proof of context-sensitivity of indexed languages [1].
We encode a list of well-formed lists as a tree, written in parenthesized notation on the tape. For
example, the list of three lists [ρ1 ρ2 ρ3 , ρ1 ρ2 ρ4 , ρ1 ρ5 ρ6 ] is encoded as ρ1 (ρ2 (ρ3 , ρ4 ), ρ5 (ρ6 )). Since thenumber of parentheses is ≤ 2n and that of commas is ≤ n where n denotes the number of nodes,
the size of this representation is O(n). When the function MATCH is recursively called, we add thecurrent e to the end of the list. The addition is represented as an addition to the rightmost path. As
an example, let e = ρ1 ρ5 ρ7 ρ8 . The common prefix ρ1 ρ5 with the current rightmost path ρ1 ρ5 ρ6 isshared, and the suffix ρ7 ρ8 is added as the rightmost child of the ρ5 -node. Then, we have a new tree
ρ1 (ρ2 (ρ3 , ρ4 ), ρ5 (ρ6 , ρ7 (ρ8 ))). Removal of the last list, which happens when MATCH returns, is thereverse operation of addition; the rightmost leaf and its ancestors that have only one descendant leaf
are removed. Note that, since by definition a well-formed list cannot be a prefix of any other wellformed lists, each well-formed list always corresponds to a leaf node of the tree. It is straightforward to
implement these two operations in linear space and in polynomial time.
Let us consider what happens if we apply this encoding to the output of a path-linear mtt. In
the algorithm MATCH we only proceed downwards in the trees, i.e., the parameter e′ to the recursive calls is always obtained by applying c-child several times to the previous parameter e. Thus,
the lists [e0 , e1 , . . . , en ] of node representations we have to store during the recursive computation
always satisfy the relation ej ∈ c-child+ (ei ) for every i < j. Let e = (r0 , ν0 ) . . . (rm , νm ) and′ , ν ′ ) be proper prefixes of different elements in the same list satisfying the cone′ = (r0′ , ν0′ ) . . . (rmmdition (here we assume that e is taken from the element preceding the one where e′ is taken). Then,orig(e) = orig(e′ ) only if e = e′ . This can be proved by contradiction. Suppose orig(e) = orig(e′ )and e ̸= e′ , and the j-th elements are the first difference between e and e′ . Recall that e′ is a prefix ofa well-formed list obtained by repeatedly applying c-child to another well-formed list, of which e is aprefix. Then it must be the case that rj = rj′ (by definition of expand, rj and rj′ are uniquely determined′′from (r0 , ν0 ) . . . (rj−1 , νj−1 ) and (r0′ , ν0′ ) . . . (rj−1, νj−1), which are equal) and νj is a proper prefix of′νj . However, due to path-linearity, the input variable at νj and νj′ must be different, which contradicts
orig(e) = orig(e′ ). Therefore, we can associate a unique node in pos(s) with each proper prefix of thelists, which means that the number of distinct proper prefixes is at most |s|. Similarly, it can be shownthat adding only to the rightmost path is sufficient for maximally sharing all common prefixes. Suppose
not, then there must be in the list three nodes of the forms e1 = e.(r, ν).e′1 , e2 = e.(r, ν ′ ).e′2 , ande3 = e.(r, ν).e′3 with ν ̸= ν ′ in this order. Note that if this happened, then the prefix e.(r, ν) would not
be shared by the rightmost addition. However, e2 ∈ c-child+ (e1 ) implies that ν is a proper prefix of ν ′ ,and by e3 ∈ c-child + (e2 ), ν ′ is a proper prefix of ν, which is a contradiction. Hence, the number ofnodes except leaves in the tree encoding equals the number of distinct proper prefixes, which is at most|s|. We can bound the number of leaves by |t|, the maximum depth of the recursion. So, the size of thetree encoding of a list of nodes is O(|s| + |t|). We can easily remember the whole list of v’s in O(|t|)
6space. Since in the lists [v1 , . . . , vn ], vi+1 is always a child node of vi , we only need to remember thechild number for each node. For example, the list [ϵ, ϵ.2, ϵ.2.1] can be encoded as [ϵ, 2, 1]. Thus, we only
need ≤ height(t) many numbers, each of which is between 1 and the maximal rank of symbols in ∆,which is a constant.
Theorem 1. Let M be a canonical, non-erasing, and path-linear mttcf. There effectively exists a nondeterministic Turing Machine which, given any s and t as input, determines whether or not (s, t) ∈ τM
in O(|s| + |t|) space and in polynomial time with respect to |s| + |t|.

4 Bounding the Size of Intermediate Trees
As explained in the Introduction, the key idea for obtaining linear-size complexity for compositions ofmtts is to bound the size of all intermediate input trees, and this is achieved by putting the mtts into
“non-deleting” forms. In the same way as for total deterministic mtts [17], we classify the “deletion” inmtts into three categories – erasing, input-deletion, and skipping (a similar classification without erasing,which is a specific use of parameters, is also used in the case of nondeterministic tts [3]). The resolutionof each kind of deletion, however, requires several new techniques and considerations compared toprevious work, due to the interaction of nondeterminism and parameters. In the rest of this paper, wefirst explain how we eliminate each kind of deletion, and then show the main results.
4.1 Erasing
We first consider “erasing” rules – rules of the form ⟨q, σ(· · · )⟩(y1 , . . . , ym ) → yi , as defined in Section 3. An application of such a rule consumes one input σ-node without producing any new output
symbols; hence it is deleting a part of the input. Note that if the rank of σ is non-zero, then a rule as
above is at the same time also input-deleting, which is handled in Section 4.2. In the case of total deterministic mtts, “non-erasing” is a normal form, i.e., for every total deterministic mtt there is an equivalent
one without erasing rules. Unfortunately, we could not find such a normal form for nondeterministic mtts
with OI semantics. Note that for OI context-free tree grammars (essentially mtts without input: think of⟨q, xi ⟩ as a nonterminal Nq , or equivalently, think of macro grammars [13] or indexed grammars [1],with trees instead of strings in right-hand sides), it has been shown [16] that there is no non-erasing
normal form: erasing grammars are strictly more powerful than non-erasing ones. To see where thedifficulty arises, let us consider the following example of a deterministic mtt and the input tree a(b, b):⟨q1 , a(x1 , x2 )⟩ → ⟨q2 , x1 ⟩(⟨q3 , x2 ⟩(B, C))⟨q2 , b⟩(y1 ) → A(y1 , y1 )⟨q3 , b⟩(y1 , y2 ) → y1 .

The ⟨q3 , b⟩-rule is erasing. The basic idea of obtaining the non-erasing normal form for total deterministic mtts is to apply all erasing rules inline where they are called in a right-hand side. That is, weremove the erasing rule and modify the q1 rule to ⟨q1 , a(x1 , x2 )⟩ → ⟨q2 , x1 ⟩(B) (plus a look-ahead check“x2 = b”). This approach does not work properly under OI-nondeterminism. Let us suppose the casewhen the ⟨q3 , b⟩-rules are nondeterministic as follows:⟨q3 , b⟩(y1 , y2 ) → y1

⟨q3 , b⟩(y1 , y2 ) → y2

⟨q3 , b⟩(y1 , y2 ) → A(y1 , y2 ).

Note that the q2 rule duplicates its argument ⟨q3 , x2 ⟩(B, C) before calling q3 , and evaluates the two copies
independently. Thus, ⟨q1 , a(b, b)⟩↓ contains all the nine trees A(t1 , t2 ) with t1 , t2 ∈ {B, C, A(B, C)}. However, the inline application of erasing rules now gives: ⟨q1 , a(x1 , x2 )⟩ → ⟨q2 , x1 ⟩(B), ⟨q1 , a(x1 , x2 )⟩ →⟨q2 , x1 ⟩(C), and ⟨q1 , a(x1 , x2 )⟩ → ⟨q2 , x1 ⟩(A(B, C)), which implies copying after evaluation of the q3
call. So, in order to perform the expansion correctly, we need some way to preserve the nondeterministic
choice after the expansion. For this purpose, we move from normal mtts to mtts with choice and failure.
The example above can be represented by an mttcf rule ⟨q1 , a(x1 , x2 )⟩ → ⟨q2 , x1 ⟩(+(B, +(C, A(B, C)))),
for instance. We will show that every mtt can be simulated by a non-erasing mttcf.
7

Lemma 2. Let M be a mtt. There exists effectively a linear tt E and a canonical mttcf M ′ such that M ′is non-erasing and τE ; τM ′ = τM . Path-linearity is preserved from M to M ′ .
Proof. The idea is, we first predict all erasing beforehand and annotate each input node by the information of erasing, by using a preprocessing linear tt. Then we replace all erasing state calls (e.g., ⟨q, x1 ⟩(u1 )with the rule ⟨q, . . .⟩(y1 ) → y1 ) in the right-hand sides of rules with the result of the erasing call (e.g.,u1 ). Note that we have to deal with nondeterminism. Suppose we have two rules ⟨q, σ⟩(y1 , y2 ) → y1and ⟨q, σ⟩(y1 , y2 ) → y2 and a state call ⟨q, x1 ⟩(u1 , u2 ) in a right-hand side. In order to preserve thenondeterminism, we replace the state call by +(u1 , u2 ).
Let M = (Q, Σ, ∆, q0 , R). We define E to be a nondeterministic linear tt with the set of states
P = [Q → 2{1,...,n} ] ∪ {p0 } (functions from Q to 2{1,...,n} where n is the maximum rank of the statesof Q, and one distinct state p0 , which is the initial state), the input alphabet Σ, the output alphabet
Σp = {(σ, p1 , . . . , pk )(k) | σ (k) ∈ Σ, pi ∈ P }, and the following rules for every σ (k) ∈ Σ and{1,...,n} ]: ⟨p, σ(x , . . . , x )⟩ → (σ, p , . . . , p )(⟨p , x ⟩, . . . , ⟨p , x ⟩) where p ∈p1 , . . . , p k ∈
1
1
1 1
k
k
k k
S [Q → 2{p0 , (q 7→ {f (r) | ⟨q, . . .⟩(. . . ) → r ∈ R})}withfrecursively
definedasfollows:
f (yi ) = {i},S′′f (δ(. . . )) = ∅, and f (⟨q , xj ⟩(r1 , . . . , rm )) = {f (ri ) | i ∈ pj (q )}. The transducer E modifies thelabel σ (k) of each input node into the form (σ (k) , p1 , . . . , pk ). The annotated information pi intuitively
means “if a state q of M is applied to the i-th child of the node, it will erase and return directly the e-thparameter for e ∈ pi (q)”. If pi (q) = ∅ then no erasing will happen. The rule of E is naturally understood
if it is read from right to left, as a bottom-up translation. Formally speaking, the following claim holds.
It is easily proved by induction on the structure of s.
Claim. (1) For each s ∈ TΣ and q ∈ Q(m) , there is a unique p ∈ P \ {p0 } such that ⟨p, s⟩↓E ̸= ∅, ande ∈ p(q) if and only if ye ∈ ⟨q, s⟩(y1 , . . . , ym )↓M . (2) Let us denote by [s] such p determined by s. The
output s′ ∈ τE (s) is unique. For b ∈ pos(s) = pos(s′ ), label(s′ , b) = (label(s, b), [s|b.1 ], . . . , [s|b.k ]).
We next define a non-erasing mttcf, using the annotation added by E. Let M ′ = (Q, Σp , ∆, q0 , R′ ) with
R′ = {⟨q, (σ, p1 , . . . , pk )(x1 , . . . , xk )⟩(y1 , . . . , ym ) → r′ | r ∈ Rq,σ , r′ ∈ ne(r), r′ ∈/ Y } where the set
ne(r) is defined inductively byne(yj ) = {yj }ne(δ(r1 , . . . , rl )) = {δ(r1′ , . . . , rl′ ) | ri′ ∈ ne(ri )}[ne(⟨q ′ , xj ⟩(r1 , . . . , rl )) = {ne(ri ) | i ∈ pj (q ′ )} ∪ {⟨q ′ , xj ⟩(nep(r1 ), . . . , nep(rl ))},and nep defined as follows: nep(yj ) = yj , nep(δ(r1 , . . . , rl )) = δ(nep(r1 ), . . . , nep(rl )), and nep(⟨q ′ ,xj ⟩(r1 , . . . , rl )) = +(u1 , +(u2 , . . . , +(uz , θ) · · · )) where {u1 , . . . , uz } = ne(⟨q ′ , xj ⟩(r1 , . . . , rl )). Intuitively, ne adds rules by replacing each top-level state calls with its argument if the state call is erasing
according to the annotation pj ’s. The other function nep does essentially the same thing for non toplevel positions, but by replacing erasing state calls with + choices instead of adding rules to preserve the
OI-nondeterminism. It should be clear from the definition that M ′ is canonical and non-erasing. Since
ne only returns a set of subtrees of a right-hand side, ne and nep never add any new nesting among state
calls, and thus M ′ is path-linear if M is.
The correctness of this construction is proved by induction on the structure of the inputStree s, byshowing that if ui ↓M = u′i ↓M ′ then ⟨q, s⟩(u1 , . . . , uk )↓M = ⟨q, τE (s)⟩(u′1 , . . . , u′k )↓M ′ ∪ {ui ↓M |yi ∈ ⟨q, s⟩(y1 , . . . , yk )↓M }. Applying this to the initial state q0 proves the equation τM = τE ; τM ′ . ⊓⊔4.2 Input-Deletion
The second kind of deletion we investigate is “input-deletion”. For instance, if there is the rule ⟨q0 , a(x1 ,x2 )⟩ → A(⟨q0 , x2 ⟩) for the initial state q0 and the input is of the form a(t1 , t2 ), then the subtree t1 isnever used for the output calculation. Although total deterministic mtts can be made nondeleting (i.e., to8

always traverse all subtrees of every input tree) by preprocessing with a deleting linear tt [17], it becomes
more difficult for nondeterministic mtts. This is because of the nondeterminism, which means that there
can be more than one possible computation for a single input tree, and we cannot avoid the situation that
one of the computations traverses all subtrees while others do not. Consider the input a(b, c(t1 , t2 )) andthe following set of rules:⟨q1 , a(x1 , x2 )⟩ → ⟨q2 , x1 ⟩(⟨q3 , x2 ⟩)⟨q2 , b⟩(y1 ) → A(y1 , y1 )⟨q3 , c(x1 , x2 )⟩ → ⟨q4 , x1 ⟩⟨q3 , c(x1 , x2 )⟩ → ⟨q4 , x2 ⟩Note that the state call for q3 is duplicated by OI semantics; even though the mtt is linear. There are threepossibilities with respect to input-deletion: either t1 is deleted (the case all duplicated q3 calls choose
the second q3 -rule), t2 is deleted (the case all choose the first rule), or no deletion occurs. We can still
construct a linear tt that does preliminarily deletion, in such a way that it nondeterministically returnsa(b, c2 (t2 )), a(b, c1 (t1 )), or a(b, c12 (t1 , t2 )) (the subscript on c identifies the non-deleted children). We
can also modify the mtt as follows⟨q3 , c1 (x1 )⟩ → ⟨q4 , x1 ⟩⟨q3 , c12 (x1 , x2 )⟩ → ⟨q4 , x1 ⟩⟨q3 , c2 (x1 )⟩ → ⟨q4 , x1 ⟩⟨q3 , c12 (x1 , x2 )⟩ → ⟨q4 , x2 ⟩in which rules using the “deleted” input subtrees are removed. Then, for the former two “deleted” instances of the input trees, the mtt is successfully non-input-deleting. But sadly, this mtt still may delete
for the last instance of the input tree, when all duplicated ⟨q3 , c12 ⟩ calls choose the same rule. The
point is, under nondeterminism, we cannot argue the input-deleting property of each transducer. Rather,
we can only argue whether each computation is input-deleting or not. This is a weaker version of thenondeletion condition used for total deterministic mtts, but it is sufficient for our purpose.
In order to speak more formally, here we define the notion of computation tree (following the methodof [3], but extending it to deal with accumulating parameters). For any finite set P , we define the ranked
alphabet P = {p(1) | p ∈ P }. Let M = (Q, Σ, ∆, q0 , R) be an mttcf and s ∈ TΣ . The set COMP(M, s)
is the set of trees comp⟨q0 , ϵ⟩↓ ⊆ T∆∪pos(s) called computation trees (or sometimes, simply computations). The derivation comp⟨q0 , ϵ⟩↓ is carried out under the following set of rewriting rules with outsidein derivation: +(u1 , u2 ) → u1 , +(u1 , u2 ) → u2 , and comp⟨q, ν⟩(⃗y ) → fν (r) for q ∈ Q, ν ∈ pos(s),r ∈ Rq,label(s,p) where fν is inductively defined as follows:fν (yi ) = yifν (δ(r1 , . . . , rk )) = ν(δ(fν (r1 ), · · · , fν (rk ))′fν (⟨q , xj ⟩(r1 , . . . , rk )) = comp⟨q ′ , ν.j⟩(fν (r1 ), · · · , fν (rk ))).
Intuitively, COMP(M, s) is the set of trees ⟨q0 , s⟩↓ where the parent of each ∆-node is a monadic
node labeled by the position in the input tree s that generated the ∆-node. For example, the output treeϵ(α(ϵ.1(β), ϵ.2(γ(ϵ(δ))))) means that the α and δ nodes are generated at the root node of the input tree,
and the β and γ nodes are generated at the first and the second child of the root node, respectively. Let
delpos be the translation that removes all ν ∈ pos(s) nodes. It is easily proved by induction on thenumber of derivation steps that delpos(COMP(M, s)) = ⟨q0 , s⟩↓M , i.e., if we remove all pos(s) nodes
from a computation tree, we obtain an output tree of the original mtt.
We say that a computation tree u is non-input-deleting if for every leaf position ν ∈ pos(s), there is
at least one node in u labeled by ν. Note that the rewriting rules of comp corresponding to erasing rules
do not generate any pos(s) node. Thus, non-input-deletion implies that not only some state is applied toevery leaf, but also a non-erasing rule of some state must be applied.

9

Lemma 3. Let M be a canonical non-erasing mttcf. There effectively exists a linear tt I and a canonicalnon-erasing mttcf M ′ such that τM = τI ; τM ′ , and for every input-output pair (s, t) ∈ τM , there exists
a tree s′ and a computation tree u ∈ COMP(M ′ , s′ ) such that (s, s′ ) ∈ τI , t = delpos(u), and u is
non-input-deleting. Also, M ′ is path-linear if M is.
Proof. Let M = (Q, Σ, ∆, q0 , R). We define I as ({d}, Σ, Σ ′ , d, U ) where Σ ′ = {(σ, i1 , . . . , im )(k) |σ (k) ∈ Σ, 1 ≤ i1 < · · · < im ≤ k} andU = {⟨d, σ(x1 , . . . , xk )⟩ → (σ, i1 , . . . , im )(⟨d, xi1 ⟩, . . . , ⟨d, xim ⟩) | (σ, i1 , . . . , im ) ∈ Σ ′ }.
The transducer I reads the input tree and nondeterministically deletes subtrees while encoding the numbers of the undeleted subtrees in the current label. We define the mttcf M ′ as (Q, Σ ′ , ∆, q0 , R′ ) where
R′ = {⟨q, (σ, i1 , . . . , im )(x1 , . . . , xm )⟩(⃗y ) → r′
| r ∈ Rq,σ such that for all top-level calls ⟨q ′ , xp ⟩ in r, p ∈ {i1 , . . . , im }, and r′ is obtained byreplacing ⟨q ′ , xij ⟩ in r with ⟨q ′ , xj ⟩ and ⟨q ′ , xp ⟩ with θ for p ∈/ {i1 , . . . , im }}.
The transducer M ′ has basically the same rules as M , except that state calls on ‘deleted’ children are
replaced by θ (or, if it is at the top-level then the rule is removed, to preserve canonicity). It should beeasy to see that M ′ is canonical and non-erasing, and preserves the path-linearity of M .
The correctness of this construction is proved as follows. Note that there is the natural one-to-one
correspondence between the set of ⟨q, σ⟩-rules of M and the set of ⟨q, (σ, i1 , . . . , im )⟩-rules of M ′ . First,
we can prove (1) τM ′ (τI (s)) ⊆ τM (s) by induction on the number of derivation steps in M ′ , showingthat for each derivation step in M ′ we can always apply the corresponding rewriting rule in M and obtainthe corresponding (i.e., differs only at state calls on ‘deleted’ nodes that are replaced with θ) sentential
form, which proves that we can obtain the same final output as τI ; τM ′ by τM . Next, we show that (2) for
any u ∈ COMP(M, s), there exists an equivalent non-input-deleting computation. Let s′ be the minimal
substructure of s that contains all nodes and their ancestors contained in u. Then s′ ∈ τI (s) assumingthat s′ is appropriately relabeled from Σ to Σ ′ as the transducer I does, and we can similarly prove that
we can obtain a computation u′ ∈ COMP(M ′ , s′ ) corresponding to u by induction on the number ofderivation steps (here, non-erasure assures that we can always choose the ‘corresponding’ rule; if a statecall comp⟨q, p⟩ is rewritten in the derivation of M , then a node labeled p′ must be generated for somedescendant p′ of p, and thus the node corresponding to p′ and its ancestor p are kept not removed in s′ ).
Then, by the construction we have delpos(u) = delpos(u′ ), and since s′ is the minimal substructure ofs that contains all nodes occurred in u, all leaf nodes of s′ occur in u′ , which means that u′ is non-inputdeleting. Note that (2) implies τM (s) ⊆ τM ′ (τI (s)). Therefore, together with (1), we have τI ; τM ′ = τM
as desired.
⊓⊔
4.3 Skipping
The third and last kind of deletion is “skipping”. A computation tree u is skipping if there is a nodeν ∈ pos(s) labeled by a rank-1 symbol such that no node in u is labeled ν. For a canonical, non-erasing,and path-linear mttcf, skipping is caused by either one of the following two forms of rules. One type isof the form ⟨q, σ(x1 )⟩(y1 , . . . , ym ) → ⟨q ′ , x1 ⟩(u1 , . . . , uv ) where ui ∈ TY ∪C , and such rules are calledskipping. The others are rules which are not skipping but are of the form ⟨q, σ(x1 )⟩(y1 , . . . , ym ) →⟨q ′ , x1 ⟩(u1 , . . . , uv ) where ui ∈ T∆∪Y ∪C , and such rules are called quasi-skipping. Note that, since themttcf is path-linear, there are no nested state calls in right-hand sides of rules for input symbols of rank 1.
Also note that if the root node of the right-hand side of a rule is not a state call, then it must be a ∆-node
since the mttcf is canonical and non-erasing. So an application of such a rule generates a ∆-node andthus a ν ∈ pos(s) node for the current input node. Therefore, it is sufficient to consider only skippingand quasi-skipping rules.
10Quasi-skipping rules may cause skipping computations due to parameter deletion: for example, consider the quasi-skipping rule ⟨q, σ(x1 )⟩(y1 ) → ⟨q ′ , x1 ⟩(δ(y1 )); if there is a q ′ -rule with a right-hand side
not using y1 , then the σ-node may be skipped. For total deterministic mtts [17], there is a “parameter
non-deleting” normal form, i.e., every total deterministic mtt is equivalent to one that uses all parametersin the right-hand sides of its rules, and thus only skipping rules (without choice nodes) were considered
there. Unfortunately, as for non-erasure, we could not find such a normal form for nondeterministic
mtts. Instead, we add some auxiliary skipping rules to mttcfs, so that we only need to consider skipping
rules. Note that quasi-skipping rules cause skipping computations only when parameters are deleted.
The idea is, if a parameter in some rule is never used for a computation, then replacing the parameterby a failure symbol θ does not change the translation, and moreover, such replacement changes a quasiskipping rule into a skipping rule. Thus we may assume that all skipping computations are caused byskipping rules, and hence we can straightforwardly extend the proofs for total deterministic mtts [17]and nondeterministic tts [3].
Lemma 4. Let M be an canonical, non-erasing, and path-linear mttcf. There exists effectively a linear
tt S and a canonical, non-erasing, and path-linear mttcf M ′ such that (1) τS ; τM ′ = τM and (2) for
every input tree s and non-input-deleting computation tree u ∈ COMP(M, s), there exists a tree s′ anda computation tree u′ such that s′ ∈ τS (s), u′ ∈ COMP(M ′ , s′ ), delpos(u′ ) = delpos(u), and u′ is both
non-input-deleting and non-skipping.
Proof. Let M = (Q, Σ, ∆, q0 , R). We define N = (Q, Σ, ∆, q0 , R ∪ R) with:R ={⟨q, σ(x1 )⟩(⃗y ) → r′ | q ∈ Q, σ ∈ Σ (1) , r ∈ Rq,σ , r is quasi-skipping,and r′ is obtained by replacing all subtrees of r of the form δ(· · · ), δ ∈ ∆ by θ}.
Obviously τM ⊆ τN , and it should be also clear that τN ⊆ τM , because in each derivation of N , we canreplace every application of R rules by the corresponding rules in R.
Furthermore, we can similarly prove that for any non-input-deleting computation u of COMP(N, s)
and U the set of rank-1 nodes of s that are skipped in u, there is a derivation that derives u and does not
apply quasi-skipping rules to any p ∈ U . Suppose a quasi-skipping rule ρ is applied to a node p ∈ U in a
derivation of u. Then, since all ∆-nodes in ρ are skipped in u (that means, they never come to top-level
position during the derivation), we can always replace the application with the corresponding skipping
rule in R (recall that it is obtained by replacing all ∆-nodes by θ) without changing the final output
computation u. Thus, for N , without loss of generality we may assume that all skipping computation
are caused by skipping rules.
SS
We define S as (H, Σ, Σ × H, h0 , U ) where H = m [Q(m) → n P(Q(n) × P({1, . . . , m})n )]with P denoting power set, h0 = q 7→ {(q, {1}, {2}, . . . , {rank(q)})}, andU = {⟨h, σ(x1 , . . . , xk )⟩ → (σ, h)(⟨h0 , x1 ⟩, . . . , ⟨h0 , xk ⟩) | σ ∈ Σ, h ∈ H}
∪ {⟨h, σ(x1 )⟩ → ⟨h′σ , x1 ⟩ | σ ∈ Σ (1) , h ∈ H}}
where h′σ is the function
h′σ = q 7→ {(q ′′ ,f (r1 ,⃗ι), . . . , f (rl ,⃗ι)}) |(q ′ , ι1 , . . . , ιn ) ∈ h(q),⟨q ′ , σ(x1 )⟩(y1 , . . . , yn ) → ⟨q ′′ , x1 ⟩(r1 , . . . , rl ) ∈ R ∪ R, ri ∈ TY ∪C }with f inductively defined as: f (yj , ι1 , . . . , ιm ) = ιj , f (θ, ι1 , . . . , ιm ) = ∅, and f (+(r1 , r2 ), ι1 , . . . , ιm )= f (r1 , ι1 , . . . , ιm ) ∪ f (r2 , ι1 , . . . , ιm ).
11

The transducer S reads the input tree and nondeterministically deletes sequences of rank-1 nodes,
while encoding the possible way to pass parameters by skipping rules. Such information on parameter passing is encoded as a function h ∈ H. For example, one possible output of S from the inputa(b(c(· · · )))) is (c, h)(· · · ), in which a and b nodes are deleted and the information is encoded in h.
Intuitive meaning of each h is, “if (q ′ , ι1 , . . . , ιn ) ∈ h(q), then when a state q were applied to the rootof the deleted sequence of rank-1 nodes with parameters t1 , . . . , tm , then N would have skipped thesequence, and reached a state q ′ with parameters ti1 , . . . tin , ij ∈ ιj for 1 ≤ j ≤ n”. The initial state h0
means that “no node was skipped so far”.
We then define M ′ as (Q, Σ × H, ∆, q0 , R′ ) where
R′ = {⟨q,(σ, h)(x1 , . . . , xk )⟩(y1 , . . . , ym ) → r[y1 /iset(ι1 ), · · · , yn /iset(ιn )]| (q ′ , ι1 , . . . , ιn ) ∈ h(q), r ∈ Rq′ ,σ }with iset({i1 , . . . , ip }) = +(yi1 , +(yi2 , · · · , +(yip , θ) · · · )). Since M is canonical, non-erasing, andpath-linear, clearly so is M ′ .
It should be easy to verify that the definition of M ′ and S follow the above intuition. The compositionτS ; τM ′ = τM and the existence of a non-skipping computation can be proved similarly as for Lemma 3.
Namely, to construct a non-skipping computation u′ from a computation u ∈ COMP(M, s), we take theintermediate tree s′ as the tree obtained from s by deleting all rank-1 nodes not contained in u. Then by
induction on the number of derivation steps, we can construct an equivalent non-skipping computationu′ ∈ COMP(M ′ , s′ ).
⊓⊔4.4Counting the Number

Lemma 5. Let M = (Q, Σ, ∆, q0 , R) be an mttcf, s an input tree, and u a non-input-deleting, nonskipping computation tree in COMP(M, s) with delpos(u) = t. Then |s| ≤ 2|t|.
Proof. Since u is non-input-deleting and non-skipping, for all nodes ν ∈ pos(s) of rank zero or one,
there exists a node labeled ν in u, and by definition of computation trees, its child node is labeled by asymbol in ∆. Thus, leaves(s) + rank1nodes(s) ≤ |t| where leaves(s) is the number of leaf nodes of sand rank1nodes(s) is the number of nodes of s labeled by rank-1 symbols. Since |s| ≤ 2 × leaves(s) +rank1nodes(s) (this holds for any tree s), we have |s| ≤ 2|t| as desired.
⊓⊔

5 Complexity of Compositions of MTTs
Lemma 6. Let K ∈ {NSPACE(n), NP} and F a class of K languages effectively closed under LT. Then
LMT(F ) and T(F ) are also in K.
Proof. Let M be a linear mtt or a tt. Note that in both cases, M is path-linear. First, we make it nonerasing; by Lemma 2, there exist a linear tt E and a canonical, non-erasing, and path-linear mttcf M1such that τE ; τM1 = τM . Next, we make each computation non-input-deleting; by Lemma 3, there
exist a linear tt I and a canonical, non-erasing, and path-linear mttcf M2 such that τI ; τM2 = τM1 .
For every (s1 , t) ∈ τM1 , there is an intermediate tree s2 and a non-input-deleting computation u ∈COMP(M2 , s2 ) such that (s1 , s2 ) ∈ τI and delpos(u) = t. Then, we make each computation nonskipping; by Lemma 4, there exist a linear tt S and a canonical, non-erasing, and path-linear mttcf M3such that τS ; τM3 = τM2 . For every non-input-deleting computation u ∈ COMP(M2 , s2 ), there is anintermediate tree s3 and a non-input-deleting, non-skipping computation u′ ∈ COMP(M3 , s3 ) such that(s2 , s3 ) ∈ τS and delpos(u′ ) = delpos(u). Altogether, we have τE ; τI ; τS ; τM3 = τM , and for every(s, t) ∈ τM there exists a tree s3 such that (s, s3 ) ∈ τE ; τI ; τS and a non-input-deleting, non-skipping
computation u′ ∈ COMP(M3 , s3 ) such that delpos(u′ ) = t. By Lemma 5, |s3 | ≤ 2|t|.
12

Let L be a language in F . To check whether t ∈ τM (L), we nondeterministically generate every tree′s of size |s′ | ≤ 2|t| and for each of them, test whether (s′ , t) ∈ τM3 and s′ ∈ (τE ; τI ; τS )(L). By Theorem 1, the former test can be done nondeterministically in O(|s′ | + |t|) = O(|t|) space and polynomial

time with respect to |t|. By the assumption that F is closed under LT, the language (τE ; τI ; τS )(L) is
also in K. Thus the latter test is in complexity K with respect to |s′ | = O(|t|).
⊓⊔Note that, for T, the same decomposition as shown in the first paragraph of the proof of Lemma 6 isalready known (Lemma 1 of [3]). And since by Theorem 1 of [3] the translation membership of a single
tt is in DSPACE(n), for T, the above result also holds for K = DSPACE(n).
Lemma 7. Let K ∈ {NSPACE(n), NP} and F a class of K languages effectively closed under LT. Then
MT(F ) is also in K and effectively closed under LT.
Proof. The closure under LT immediately follows from the following known results: MT = Dt MT ; T(Corollary 6.12 of [12]), T ; LT = Dt QREL ; T (Lemma 2.11 of [9]), and Dt MT ; Dt QREL ⊆ Dt MT(Lemma 11 of [11]). By Lemma 2.11 of [9] and Theorem 2.9 of [8], T ; LT ⊆ LT ; T, which implies that
T(F ) is also closed under LT. By the decomposition MT = Dt T ; LMT (page 138 of [12]), MT(F ) ⊆LMT(T(F )). By applying Lemma 6 twice, LMT(T(F )) is in K.
⊓⊔
Theorem 8. MT∗ (REGT) ⊆ NSPACE(n) ∩ NP-complete.
Proof. The class REGT is closed under LT (Propositions 16.5 and 20.2 of [15]) and is in NSPACE(n) ∩NP (see, e.g., [15]). By induction on k ≥ 1 it follows from Lemma 7 that MTk (REGT) is in NSPACE(n)and NP. As noted in the Introduction, NP-hardness follows from [23] and the fact that the indexedlanguages, which are equivalent to the yields of context-free-tree languages under OI-derivation, are in
MT2 (REGT).
⊓⊔
Although we only have considered outside-in evaluation order up to here, the previous result holds forcompositions of mtts in inside-out evaluation order. This is because MT∗IO = MT∗ by Theorem 7.3
of [12], where MTIO denotes the class of translations realized by mtts in inside-out evaluation order.
Corollary 9. MT∗IO (REGT) ⊆ NSPACE(n) ∩ NP-complete.
The yield translation, which translates a tree into its string of leaf labels from left to right (seen as amonadic tree), is in Dt MT. Therefore the output string languages yield(MT∗ (REGT)) of mtts are also inthe same complexity class as Theorem 8. Especially, this class contains the IO- and OI- hierarchies [6].
Note that the IO-hierarchy is in Dt MT∗ (REGT) and hence in DSPACE(n) by Corollary 17 of [17]. Since
the first level of the OI-hierarchy are the indexed languages [13] which are NP-complete [23], we obtainthe following.
Corollary 10. The OI-hierarchy is in NSPACE(n) ∩ NP-complete.
Acknowledgment This work was partly supported by the Japan Society for the Promotion of Science.

References
1. A. V. Aho. Indexed grammars—an extension of context-free grammars. J. ACM, 15:647–671, 1968.
2. P. R. J. Asveld. Time and space complexity of inside-out macro languages. Int. J. Comp. Math., 10:3–14, 1981.
3. B. S. Baker. Generalized syntax directed translation, tree transducers, and linear space. SIAM J. Comp., 7:376–391, 1978.
4. G. Busatto, M. Lohrey, and S. Maneth. Efficient memory representation of XML document trees. Inf. Syst., 33:456–474,
2008.
5. B. Courcelle. Monadic second-order definable graph transductions: A survey. Th. Comp. Sc., 126:53–75, 1994.
6. W. Damm. The IO- and OI-hierarchies. Th. Comp. Sc., 20:95–207, 1982.
7. F. Drewes and J. Engelfriet. Decidability of the finiteness of ranges of tree transductions. Inf. and Comp., 145:1–50, 1998.
8. J. Engelfriet. Bottom-up and top-down tree transformations – a comparison. Math. Sys. Th., 9:198–231, 1975.

13

9. J. Engelfriet. Top-down tree transducers with regular look-ahead. Math. Sys. Th., 10:289–303, 1977.
10. J. Engelfriet. The complexity of languages generated by attribute grammars. SIAM J. Comp., 15:70–86, 1986.
11. J. Engelfriet and S. Maneth. Output string languages of compositions of deterministic macro tree transducers. J. Comp.
Sys. Sci., 64:350–395, 2002.
12. J. Engelfriet and H. Vogler. Macro tree transducers. J. Comp. Sys. Sci., 31:71–146, 1985.
13. M. J. Fischer. Grammars with Macro-Like Productions. PhD thesis, Harvard University, Cambridge, 1968.
14. Z. Fülöp and H. Vogler. Syntax-Directed Semantics: Formal Models Based on Tree Transducers. Springer-Verlag, 1998.
15. F. Gécseg and M. Steinby. Tree languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages,
Vol 3: Beyond Words, pages 1–68. Springer-Verlag, 1997.
16. B. Leguy. Grammars without erasing rules. the OI case. In Trees in Algebra and Programming, 1981.
17. S. Maneth. The complexity of compositions of deterministic tree transducers. In FSTTCS, 2002.
18. S. Maneth, A. Berlea, T. Perst, and H. Seidl. XML type checking with macro tree transducers. In PODS, 2005.
19. S. Maneth and G. Busatto. Tree transducers and tree compressions. In FoSSaCS, 2004.
20. T. Milo, D. Suciu, and V. Vianu. Typechecking for XML transformers. In PODS, 2000.
21. T. Perst and H. Seidl. Macro forest transducers. Information Processing Letters, 89:141–149, 2004.
22. W. C. Rounds. Mappings and grammars on trees. Math. Sys. Th., 4:257–287, 1970.
23. W. C. Rounds. Complexity of recognition in intermediate-level languages. In FOCS, 1973.
24. J. W. Thatcher. Generalized2 sequential machine maps. J. Comp. Sys. Sci., 4:339–367, 1970.

14