Foundations of Software Technology and Theoretical Computer Science (Bangalore) 2008.
Editors: R. Hariharan, M. Mukund, V. Vinay; pp 244-255

The Complexity of Tree Transducer
Output Languages
Kazuhiro Inaba1 and Sebastian Maneth2,3
1 The University of Tokyo, kinaba@is.s.u-tokyo.ac.jp
2 National ICT Australia, sebastian.maneth@nicta.com.au
3 University of New South Wales, Sydney

A BSTRACT. Two complexity results are shown for the output languages generated by compositionsof 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 andrecently have been applied to XML transformations and query languages [18, 21]. Mtts are a
combination of top-down tree transducersand 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 treetranslations which contains most known classes of tree translations such as those realized
by attribute grammars, by MSO-definable tree translations [5], or by pebble tree transducers [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 obtaina string language. The string languages obtained in this way from the mtt-hierarchy forma 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 the translation “yield” which turns a tree into its frontier string (seenas 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, the yields of context-freetree languages under IO-derivation) and the string languages generated by attribute grammars. Both of these classes are LOG(CFL)-complete by [2] and [10], respectively. Anothersubclass of our class is that of OI-macro languages, which are equivalent to the indexedlanguages [1], by [13]. This class is known to be NP-complete [22]. Hence, our class is
NP-hard too (even already at level 2). Our first main result is that output languages ofthe mtt-hierarchy are NP-complete; thus, the complexity remains in NP when going fromc

K. Inaba and S. Maneth; licensed under Creative Commons License-NC-ND

FSTTCS 2008
IARCS Annual Conference onFoundations of Software Technology and Theoretical Computer Science
http://drops.dagstuhl.de/opus/volltexte/2008/1757

K. I NABA AND S. M ANETHFSTTCS 2008

indexed languages to the full mtt-hierarchy. In terms of space complexity, 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) and thus are context-sensitive. The approach of our proof can be seen asa generalization of the proofs in [3] and [17]; moreover, we make essential use of the ideaof compressed representation of backtracking information, used by Aho in [1] for showingthat the indexed languages are in NSPACE(n).
We first solve the “translation membership” problem for a single mtt M. That is, weshow that, given trees s and t, we can determine whether or not the pair (s, t) is in M’stranslation, in linear space and polynomial time with respect to |s| + |t| on a nondeterministic Turing Machine (|s| denotes the size of the tree s). The challenge here is the spacecomplexity; we use a compressed representation of M’s output trees for input s, inspiredby [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 of index stringsin [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 know that 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 such intermediate input trees.
This is achieved by putting the mtts in certain normal forms such that they do not deletemuch of their input, in the sense that every output tree t has a corresponding input tree ofsize only linearly larger than |t|. Although our approach is similar to [17], the existence ofcontext parameters and nondeterminism together adds new challenges in every step of theproof. For example, consider the mtt Mdexp with the following three rules r0 , r1 , and r2 :hq0 , a( x )i → hq, x i(hq, x i(e))
hq, a( x )i(y) → hq, x i(hq, x i(y))

(r0 )
(r1 )

hq, ei(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 forma(a(· · · a(e) · · · )) as input (with n occurrences of a) and generates a full binary tree of height
2n (note that, without parameters, the height growth can only be linear) with each non-leaf
node arbitrarily labeled either b or c. Therefore, the size of the set of possible output trees is
2n22 . To decide whether (s, t) ∈ τMdexp for given trees s and t, we essentially have to find thecorrect 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 in the 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.

245

246

T HE C OMPLEXITY OF T REE T RANSDUCER O UTPUT L ANGUAGES

2

Preliminaries

The notation used in this paper will be the same as that used in [17], except that we denotethe sequential composition by the operator ; instead of ◦, and the label of a tree node bylabel(t, ν) instead of t[ν]. We denote by pos(t) ⊆ N ∗ the set of nodes of a tree t.
A macro tree transducer (mtt) M is a tuple ( Q, Σ, ∆, q0 , R), where Q is the ranked alphabetof states, Σ and ∆ are the input and output alphabets, q0 ∈ Q(0) is the initial state, and R is
the finite set of rules of the form hq, σ( x1 , . . . , xk )i(y1 , . . . , ym ) → r where q ∈ Q(m) , σ ∈ Σ(k) ,and r is a tree in T∆∪(Q×Xk )∪Ym . Rules of such form are called hq, σ i-rules, and the set ofright-hand sides of all hq, σ i-rules is denoted by Rq,σ . We always assume Σ(0) and ∆(0) (andthus, TΣ and T∆ ) are non-empty. The rules of M are used as term rewriting rules in theusual way. We denote by ⇒ M the derivation relation of M on T(Q×TΣ )∪∆ , and by u↓ M the set{t ∈ T∆ | u ⇒∗M t}. Note that “state-calls” hq, xi i can be nested and therefore different ordersof 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 ∈ hq0 , si↓ M }. We denote by MT theclass of translations realized by mtts. An mtt is called a top-down tree transducer (tt) if allits states are of rank 0; the corresponding class of translations is denoted by T. We call an
mtt deterministic (total, respectively) if for every hq, σi ∈ 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 is linear (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.
For a technical reason, we define a slight extension of mtts. We fix the set of choicenodes C = {θ (0) , +(2) } and assume it to be disjoint with other alphabet. An mtt with choiceand failure (mttcf ) M is a tuple ( Q, Σ, ∆, q0 , R) defined as for normal mtts, except that theright-hand sides of rules are trees in T∆∪(Q×Xk )∪Ym ∪C . The derivation relations (⇒ M and↓ M ) and the realized translation (τM ) are defined similarly 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 outsidein 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 canonicalif 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 any MT
generating trees in T∆ can be regarded as a Dt MT generating “choice trees” in T∆∪C ; a choicetree each of the choice trees denotes the set of possible output trees by interpreting θ as theempty set and +(c1 , c2 ) as the union of the sets denoted by c1 and c2 .

3Complexity of a Single MTT

In this section we show that for any canonical mttcf M having properties called path-linear
and non-erasing, there is a nondeterministic Turing Machine that decides whether a given

K. I NABA AND S. M ANETHFSTTCS 2008

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 thecase 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 achievedby 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). Notethat neither (1) nor (2) hold for mtts; the recursion depth can be exponential and the actual
parameters passed to each state call must also be remembered for backtracking.
Here we concentrate on a restricted class of mttcfs, namely, canonical, non-erasing, andpath-linear mttcfs, which is exactly the class of mttcfs needed later in Section 4, to obtainthe complexity result for the output languages of the mtt-hierarchy. For a canonical mtt,
we define a right-hand side of a rule to be 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 hq, xi i(· · · h p, x j i(· · · ) · · · ) in its rules implies i 6= j.
Making MTTCFs Total Deterministic Let M be a canonical, non-erasing, and pathlinear mttcf. It is easy to see that we can always construct a total deterministic mttcf M′
equivalent to M by simply taking hq, σ(· · · )i(· · · ) → +(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(ν′ ) 6= +. Pathlinearity 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).
Let N be a total, deterministic, non-erasing, and path-linear mtt with output alphabet∆ ∪ C and let s be an input tree. Let E = {(r, ν) | q ∈ Q, σ ∈ Σ, r ∈ Rq,σ , ν ∈ pos(r )}. Fora 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 the smallest index satisfying label(rk , νk ) ∈/ Q × X (or, let k = n + 1 when alllabels are in Q × X) and i j is the number such that hq, xi j i = label(r j , νj ) for some q. We call e

247

248

T HE C OMPLEXITY OF T REE T RANSDUCER O UTPUT L ANGUAGES
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 or a “call stack” of the mtt N. Each node of τN (s) canbe represented by a well-formed list, which can be 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 nonlinear 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 ith 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 ) wherelabel(rn , νn ) = hq, x j i ∈ Q × X, we define expand(e) = (r0 , ν0 ) . . . (rn , νn )(rn+1 , ǫ) where rn+1
is the right-hand side of the unique hq, label(s, orig(e))i-rule. Then, the operation c-child(e, i )is realized by the following algorithm: first apply downi to e, then repeatedly apply pop as
long as possible, and then repeatedly apply expand as long as possible. The non-erasure 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 is in ∆ ∪ C. Since the length of a well-formed list is bounded by |s| and pop (andexpand, 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, the representation of the root of τN (s) is obtained inpolynomial time by repeatedly applying expand as long as possible to e0 = (r0 , ǫ) wherer0 denotes the right-hand side of the unique hq0 , label(s, ǫ)i-rule. Note that a similar list
representation is used in the proof of Theorem 3 in [4].
Matching Algorithm with NP Time Com- MATCH (e, v)
1: while label(e) = + do
plexity Let t ∈ T∆ . Figure 1 shows the non- 2:e ← c-child(e, k) where k = 1 or 2,
nondeterministically chosen
deterministic algorithm MATCH that decides,
3: if c-label(e) 6= label(v) thengiven a well-formed list e and a node v of 4:
return falset, whether the set of trees represented by the 5: else if rank(label(v)) = 0 then6:
return truechoice tree at e contains the subtree of t rooted 7:
else
for i = 1 to rank(label(v)) do
at v. The operations c-label and c-child are de- 8:9:
if not MATCH (c-child(e, i ), child(v, i )) thenfined as above. The operations label, rank, and 10:
return false
child are basic tree operations, assumed to run in 11:
return truepolynomial time with respect to |t|. If we apply
Figure 1: Matching Algorithm
MATCH to the representations of the root nodesof τN (s) and v = ǫ, we can decide whether(s, t) ∈ τM . Since this is the standard top-down recursive comparison of two trees, thecorrectness of the algorithm should be clear.
In each nondeterministic computation, MATCH is called once for each node of t. In
each call, the while-loop iterates at most c|s| times for a constant c. This is due to nonerasure, i.e., for every Y-node in right-hand sides there exists a non-+ ancestor node. If weonce expand a list for obtaining c-child, we never see Y-nodes in right-hand sides (thus neverK. I NABA AND S. M ANETHFSTTCS 2008pop) 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), andafter that no pop is applied, i.e., the only operations applied are expand or down. In otherwords, it has to be in the regular set (pop|down)∗ (expand|down)∗ . However, since the lengthof 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, the numbers 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 haveto remember e (which costs O(|s|) space) and v (O(log(|t|)) space at least, depending on thetree node representation) in each step 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 the first two elements with the root node
representation. We show that if we store lists of nodes with common prefixes maximallyshared, then, in the case of path-linear mtts, their space consumption becomes O(|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 thetape. 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 the number 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 isrecursively called, we add the current 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 is shared, 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 ))). Removalof the last list, which happens when MATCH returns, is the reverse 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 well-formed 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 parametere′ 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 e j ∈ c-child+ (ei ) for every i < j. Let′ , ν′ ) be proper prefixes of different elementse = (r0 , ν0 ) . . . (rm , νm ) and e′ = (r0′ , ν0′ ) . . . (rmmin the same list satisfying the condition (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 beproved by contradiction. Suppose orig(e) = orig(e′ ) and e 6= e′ , and the j-th elements are
the first difference between e and e′ . Recall that e′ is a prefix of a well-formed list obtainedby repeatedly applying c-child to another well-formed list, of which e is a prefix. Then it

249

250

T HE C OMPLEXITY OF T REE T RANSDUCER O UTPUT L ANGUAGES
must be the case that r j = r ′j (by definition of expand, r j and r ′j are uniquely determined from(r0 , ν0 ) . . . (r j−1 , νj−1 ) and (r0′ , ν0′ ) . . . (r ′j−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) witheach proper prefix of the lists, which means that the number of distinct proper prefixes is
at most |s|. Similarly, it can be shown that adding only to the rightmost path is sufficientfor maximally sharing all common prefixes. Suppose not, then there must be in the list
three nodes of the forms e1 = e.(r, ν).e1′ , e2 = e.(r, ν′ ).e2′ , and e3 = e.(r, ν).e3′ with ν 6= ν′ inthis order. Note that if this happened, then the prefix e.(r, ν) would not be shared by therightmost addition. However, e2 ∈ c-child+ (e1 ) implies that ν is a proper prefix of ν′ , andby e3 ∈ c-child + (e2 ), ν′ is a proper prefix of ν, which is a contradiction. Hence, the numberof nodes 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 the tree encoding of a list of nodes is O(|s| + |t|). We caneasily remember the whole list of v’s in O(|t|) space. Since in the lists [v1 , . . . , vn ], vi+1 isalways a child node of vi , we only need to remember the child 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 isa constant.
T HEOREM 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 (s, t) ∈ τM in O(|s| + |t|) space and in polynomial time with respect to |s| + |t|.

4

Complexity of Compositions of MTTs

As explained in the Introduction, the key idea for obtaining linear-size complexity for compositions of mtts is to bound the size of all intermediate input trees, and this is achievedby putting the mtts into “non-deleting” forms. In the same way as for total deterministic
mtts [17], we classify the “deletion” in mtts into three categories – erasing, input-deletion, andskipping (a similar classification without erasing, which is a specific use of parameters, isalso used in the case of nondeterministic tts [3]). The resolution of each kind of deletion,
however, requires several new techniques and considerations compared to previous work,
due to the interaction of nondeterminism and parameters. In the rest of this paper, we first
explain how we eliminate each kind of deletion, and then show the main results.
Erasing We first consider “erasing” rules – rules of the form hq, σ(· · · )i(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 therank of σ is non-zero, then a rule as above is at the same time also input-deleting, whichis handled in Section 4. 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: thinkof hq, xi i as a nonterminal Nq , or equivalently, think of macro grammars [13] or indexed

K. I NABA AND S. M ANETHFSTTCS 2008

grammars [1], with trees instead of strings in right-hand sides), it has been shown [16] that
there is no non-erasing normal form. The problems is, that “inline expansion”, as used toobtain non-erasing total deterministic mtts, generates copies of evaluated trees, which may
not correctly model the OI semantics of the original transducer. Therefore, we move fromnormal mtts to mtts with choice and failure. The example above can be represented by an mttcf
rule hq1 , a( x1 , x2 )i → hq2 , x1 i(+(B, +(C, A(B, C)))), for instance. We will show that every mtt
can be simulated by a non-erasing mttcf.
L EMMA 2. Let M be a mtt. There effectively exists 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′ .
P ROOF. The idea is, we first predict all erasing beforehand and annotate each input nodeby the information of erasing, by using a preprocessing linear tt. Then we replace all erasingstate calls (e.g., hq, x1 i(u1 ) with the rule hq, . . .i(y1 ) → y1 ) in the right-hand sides of ruleswith the result of the erasing call (e.g., u1 ). Note that we have to deal with nondeterminism.
Suppose we have two rules hq, σi(y1 , y2 ) → y1 and hq, σ i(y1 , y2 ) → y2 and a state callhq, x1 i(u1 , u2 ) in a right-hand side. In order to preserve the nondeterminism, we replace thestate call by +(u1 , u2 ).
Let M = ( Q, Σ, ∆, q0 , R). We define E to be a nondeterministic linear tt with the setof states P = [ Q → 2{1,...,n} ] ∪ { p0 } (functions from Q to 2{1,...,n} where n is the maximum rank of the states of 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 thefollowing rules for every σ(k) ∈ Σ and p1 , . . . , pk ∈ [ Q → 2{1,...,n} ]: h p, σ( x1 , . . . , xk )i →S(σ, p1 , . . . , pk )(h p1 , x1 i, . . . , h pk , xk i) where p ∈ { p0 , (q 7→ { f (r ) | hq, . . .i(. . . ) → r ∈ R})}
with f recursively defined as follows: f (yi ) = {i }, f (δ(. . . )) = ∅, and f (hq′ , x j i(r1 , . . . , rm ))S= { f (ri ) | i ∈ p j (q′ )}. The transducer E modifies the label σ(k) of each input node into theform (σ(k) , p1 , . . . , pk ). The annotated information pi intuitively means “if a state q of M isapplied to the i-th child of the node, it will erase and return directly the e-th parameter fore ∈ 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 h p, si↓ E 6=∅, and e ∈ p(q) if and only if ye ∈ hq, si(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 ]) where s|ν is the subtree of s rooted at the node ν.
Then, let M′ = ( Q, Σ p , ∆, q0 , R′) with R′ = {hq, (σ, p1 , . . . , pk )( x1 , . . . , xk )i(y1 , . . . , ym ) →r ′ | r ∈ Rq,σ , r ′ ∈ ne(r ), r ′ ∈/ Y } where the set ne(r ) is defined inductively by ne(r ) = {y j }S
if r = y j and ne(r ) = {δ(r1′ , . . . , rl′ ) | ri′ ∈ ne(ri )} if r = δ(r1 , . . . , rl ), and ne(r ) = {ne(ri ) |i ∈ p j (q′ )} ∪ {hq′ , x j i(nep(r1 ), . . . , nep(rl ))} if r = hq′ , x j i(r1 , . . . , rl ), and nep defined as follows: nep(y j ) = y j , nep(δ(r1 , . . . , rl )) = δ(nep(r1 ), . . . , nep(rl )), and nep(hq′ , x j i(r1 , . . . , rl )) =+(u1 , +(u2 , . . . , +(uz , θ )· · ·)) where {u1 , . . . , uz} = ne(hq′ , x j i(r1 , . . . , rl )). The correctness of
this construction is proved by induction on the structure of the input tree s.
Input-Deletion The second kind of deletion we investigate is “input-deletion”. For
instance, if there is the rule hq0 , a( x1 , x2 )i → A(hq0 , x2 i) for the initial state q0 and the input

251

252

T HE C OMPLEXITY OF T REE T RANSDUCER O UTPUT L ANGUAGES
is of the form a(t1 , t2 ), then the subtree t1 is never used for the output calculation. Although
total deterministic mtts can be made nondeleting (i.e., to always traverse all subtrees of every input tree) by preprocessing with a deleting linear tt [17], it becomes more difficult for
nondeterministic mtts. The point is, under nondeterminism, we cannot argue the inputdeleting property of each transducer. Rather, we can only argue whether each computation is
input-deleting or not. This is a weaker version of the nondeletion 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 method of [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 comphq0 , ǫi↓ ⊆ T∆∪ pos(s) called
computation trees (or sometimes, simply computations). The derivation comphq0 , ǫi↓ is carriedout under the following set of rewriting rules with outside-in derivation: +(u1 , u2 ) → u1 ,+(u1 , u2 ) → u2 , and comphq, νi(~y) → f ν (r ) for q ∈ Q, ν ∈ pos(s), r ∈ Rq,label(s,p) wheref ν is inductively defined as f ν (yi ) = yi , f ν (δ(r1 , . . . , rk )) = ν(δ( f ν (r1 ), · · · , f ν (rk )), andf ν (hq′ , x j i(r1 , . . . , rk )) = comphq′ , ν.ji( f ν (r1 ), · · · , f ν (rk ))). Intuitively, COMP( M, s) is the setof trees hq0 , si↓ 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 provedby induction on the number of derivation steps that delpos(COMP( M, s)) = hq0 , si↓ M , i.e., if
we remove all pos(s) nodes from a computation tree, we obtain an output tree of the originalmtt.
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 compcorresponding to erasing rules do not generate any pos(s) node. Thus, non-input-deletion
implies that not only some state is applied to every leaf, but also a non-erasing rule of somestate must be applied.
L EMMA 3. Let M be a canonical non-erasing mttcf. There effectively exists a linear tt I
and a canonical non-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.
P ROOF. Let M = ( Q, Σ, ∆, q0 , R). We define I as ({d}, Σ, Σ′ , d, U ) where Σ′ = {(σ, i1 , . . . ,im )(m) | σ(k) ∈ Σ, 1 ≤ i1 < · · · < im ≤ k} and U = {hd, σ( x1 , . . . , xk )i → (σ, i1 , . . . , im )(hd, xi1 i,. . . , hd, xim i) | (σ, i1 , . . . , im ) ∈ Σ′ }. The transducer I reads the input and nondeterministically deletes subtrees while encoding the numbers of the non-deleted subtrees in the current
label. We define the mttcf M′ as ( Q, Σ′ , ∆, q0 , R′ ) where
R′ = {hq, (σ, i1 , . . . , im )( x1 , . . . , xm )i(~y) → r ′| r ∈ Rq,σ such that for all top-level calls hq′ , x p i in r, p ∈ {i1 , . . . , im }, and r ′ is obtainedby replacing hq′ , xi j i in r with hq′ , x j i and hq′ , x p i with θ for p ∈/ {i1 , . . . , im }}.

K. I NABA AND S. M ANETHFSTTCS 2008

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 be easy to see that M′ is canonical and non-erasing, and preserves
the path-linearity of M. The correctness of the construction is proved by taking as s′ theminimal substructure of s that contains all nodes used for calculating t.
Skipping The third and last kind of deletion is “skipping”. A computation tree u isskipping if there is a node ν ∈ pos(s) labeled by a rank-1 symbol such that no node in u islabeled ν. For a canonical, non-erasing, and path-linear mttcf, skipping is caused by either
one of the following two forms of rules. One type is of the form hq, σ( x1 )i(y1 , . . . , ym ) →hq′ , x1 i(u1 , . . . , uv ) where ui ∈ TY ∪C , and such rules are called skipping. The others arerules which are not skipping but are of the form hq, σ( x1 )i(y1 , . . . , ym ) → hq′ , x1 i(u1 , . . . , uv )where ui ∈ T∆∪Y ∪C , and such rules are called quasi-skipping. Note that, since the mttcf ispath-linear, there are no nested state calls in right-hand sides of rules for input symbols ofrank 1. Also note that if the root node of the right-hand side of a rule is not a state call, thenit must be a ∆-node since the mttcf is canonical and non-erasing. So an application of sucha rule generates a ∆-node and thus a ν ∈ pos(s) node for the current input node. Therefore,
it is sufficient to consider only skipping and quasi-skipping rules.
Quasi-skipping rules may cause skipping computations due to parameter deletion: forexample, consider the quasi-skipping rule hq, σ( x1 )i(y1 ) → hq′ , x1 i(δ(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 parameters in 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 parameter by a failure symbol θ does not change the translation, and moreover,such replacement changes a quasi-skipping rule into a skipping rule.
L EMMA 4. Let M be an canonical, non-erasing, and path-linear mttcf. There effectively exists 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′ and a 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.
P ROOF. First, we construct a new set R of skipping rules from quasi-skipping rules of M,
by replacing all ∆ nodes in each quasi-skipping rule by the failure symbol θ. We then provethat adding rules in R to M does not change the translation, and moreover, the addition
implies that all skipping computations of M have a derivation that does not apply quasiskipping rules to skipped nodes. Thus we may assume that all skipping computations arecaused by skipping rules, and hence we can straightforwardly extend the proofs for total
deterministic mtts [17] and nondeterministic tts [3].

253

254

T HE C OMPLEXITY OF T REE T RANSDUCER O UTPUT L ANGUAGES
L EMMA 5. Let M = ( Q, Σ, ∆, q0 , R) be an mttcf, s an input tree, and u a non-input-deleting,non-skipping computation tree in COMP( M, s) with delpos(u) = t. Then |s| ≤ 2|t|.
P ROOF. Since u is non-input-deleting and non-skipping, for all nodes ν ∈ pos(s) of rankzero or one, there exists a node labeled ν in u, and by definition of computation trees, its
child node is labeled by a symbol in ∆. Thus, leaves(s) + rank1nodes(s) ≤ |t| where leaves(s)is the number of leaf nodes of s and rank1nodes(s) is the number of nodes of s labeled byrank-1 symbols. Since |s| ≤ 2 × leaves(s) + rank1nodes(s) (this holds for any tree s), we have|s| ≤ 2|t| as desired.
Main Results
L EMMA 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.
P ROOF. Let M be a linear mtt or a tt. Note that in both cases, M is path-linear. First, we
make it non-erasing; by Lemma 2, there exist a linear tt E and a canonical, non-erasing, andpath-linear mttcf M1 such that τE ; τM1 = τM . Next, we make each computation non-inputdeleting; 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 anda non-input-deleting computation u ∈ COMP( M2 , s2 ) such that (s1 , s2 ) ∈ τI and delpos(u) =t. Then, we make each computation non-skipping; by Lemma 4, there exist a linear tt S anda canonical, non-erasing, and path-linear mttcf M3 such that τS ; τM3 = τM2 . For every noninput-deleting computation u ∈ COMP( M2 , s2 ), there is an intermediate tree s3 and a noninput-deleting, non-skipping computation u′ ∈ COMP( M3 , s3 ) such that (s2 , s3 ) ∈ τS anddelpos(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|.
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 isclosed 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 result is known to hold also for K = DSPACE(n) (Theorem 1 of [3]).
L EMMA 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.
P ROOF. 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.
By REGT, we denote the class of regular tree languages [15].

K. I NABA AND S. M ANETHFSTTCS 2008

T HEOREM 8. MT∗ (REGT) ⊆ NSPACE(n) ∩ NP-complete.
P ROOF. 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 [22] and the fact that the indexed languages, which are equivalent to the yields ofcontext-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 for compositions of mtts in inside-out evaluation order. This is because MTIO=∗
MT by Theorem 7.3 of [12], where MTIO denotes the class of translations realized by mtts
in inside-out evaluation order. The yield translation, which translates a tree into its string ofleaf labels from left to right (seen as a monadic tree), is in Dt MT. Therefore the output string
languages yield(MT∗ (REGT)) of mtts are also in the 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]. The first level of the
OI-hierarchy are the indexed languages [13] which are NP-complete [22].
C OROLLARY 9. The OI-hierarchy is in NSPACE(n) ∩ NP-complete.
Thanks 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. TCS, 126:53–75, 1994.
[6] W. Damm. The IO- and OI-hierarchies. TCS, 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.
[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. Complexity of recognition in intermediate-level languages. In FOCS, 1973.
This work is licensed under the Creative Commons AttributionNonCommercial-No Derivative Works 3.0 License.

255