The complexity of the exponential output size problem for top-down and bottom-up tree transducers.
The exponential output size problem is to determine whether the size of output trees of a tree transducer grows exponentially in the size of input trees. In this paper the complexity of this problem is studied. It is shown to be NL-complete for total top-down tree transducers, DEXPTIME-complete for general top-down tree transducers, and P-complete for bottom-up tree tranducers. Copyright 2001 Academic Press.
Introduction
Top-down and bottom-up tree transducers were introduced in the late sixties
by Rounds and Thatcher [13, 16, 17, 18] as a generalisation of finite-state transducers
on strings. The main motivation was to provide a simple formal model
of syntax-directed transformational grammars in mathematical linguistics and
of syntax-directed translation in compiler construction (for the latter, see the
recent book by F-ul-op and Vogler [8]). Since that time it has turned out that
tree transducers are a useful tool for many other areas, too, and their properties
and extensions have been studied by a variety of authors. For references see,
e.g., [9, 8].
For the most part of this paper top-down tree transducers are studied. As
mentioned above, they can be seen as a generalisation of finite-state string
transducers (also called generalised sequential machines) to trees 1 . Like those,
top-down tree transducers are one-way devices which process their input in one
direction, using a finite number of states. However, while string transducers usually
process their input from left to right, top-down tree transducers transform
input trees to output trees from the root towards the leaves (which, of course, is
the reason for calling them top-down tree transducers). Roughly speaking, the
Partially supported by the EC TMR Network GETGRATS (General Theory of Graph
Transformation Systems) and the ESPRIT Working Group APPLIGRAPH through the University
of Bremen.
y A short version of this paper was presented on FCT'99 [3].
1 In this context, a tree is a labelled, ordered tree whose labels are taken from a ranked
alphabet (or signature), i.e., a term.
string case is obtained by considering monadic input and output trees (which
can be viewed as "vertical strings").
Although the generalisation is quite a direct one, the fact that trees instead of
strings are considered makes a rather crucial difference in certain respects. This
concerns, for example, closure properties which hold in the string case but do
not carry over to top-down tree transducers. For instance, an infinite hierarchy
is obtained by considering compositions of top-down tree transducers (see [5]).
Another important difference is that, intuitively, the computations of top-down
tree transducers are usually ramifying: when the topmost node of an input tree
has been processed, the computation proceeds on all subtrees in parallel. In fact,
subtrees can also be deleted or copied. One of the most distinct consequences
of this fact is that, in contrast to the string case, the size of output trees of a
top-down tree transducer is not necessarily linearly bounded in the size of its
input trees. As an example, consider the two rules
fl[a] !a (which should be considered as term rewrite rules in the usual way).
Here, fl is a special symbol of rank 1 called a state and f; g; a are symbols of
rank 2, 1, and 0, respectively. Without going into the details it should be clear
that these rules transform the monadic tree of height n into a
complete binary tree of the same height. Thus, the output size is exponential in
the size of input trees. It follows directly from the definition of top-down tree
transducers that an exponential size of output trees is the maximum growth they
can achieve. However, it is as well possible to build a top-down tree transducer
whose maximum output size is given by a polynomial of degree k, for any given
N. As a simple example, consider the rules
using states fl and fl 0 . Taking fl to be the initial state, an input tree
of size n+ 1 is turned into the output tree f each
t i is a tree In other words, the size of output trees is
quadratic in the size of input trees.
In this paper the complexity of the corresponding decision problem is studied:
given a top-down tree transducer td , is its output size os td (n) exponential in
the size n of input trees? It turns out that this problem is efficiently solvable
(namely NL-complete 2 ) for total top-down tree transducers, but is very
hard (namely DEXPTIME-complete) in general. Using known results, the NL-
respectively DEXPTIME-hardness of the two variants is relatively easy to es-
tablish, but some effort is necessary in order to prove that these resources are
indeed sufficient.
Apart from being interesting in their own right, these results can be useful if
tree transducers are considered as a model of syntax-directed translation [8].
For practical reasons, an exponential behaviour of a translation is often not
acceptable. For example, the translation of expressions of some high-level programming
language into primitive instructions is of little practical use if the
2 Throughout this paper, completeness means log-space completeness.
output code is of exponential size. Closely related is the use of tree transducers
in order to generate trees which are interpreted as expressions over some
domain (see, e.g., [4, 2]). In order to estimate the evaluation costs of the generated
expressions (and the costs of computing the tree transduction itself) it
is necessary to estimate the size of output trees, i.e., to solve the exponential
output size problem. In fact, the top-down tree transducers which are used in
these two areas are often total for natural reasons. Therefore, the result that
the exponential output size problem is in NL for this class of tree transducers
may be of particular interest.
For their notion of generalised syntax-directed translations, which are closely
related to total deterministic top-down tree transducers, Aho and Ullman investigated
output size already in [1]. They showed that the output size of a
generalised syntax-directed translation is either polynomial or exponential [1,
Theorem 5.2]. The same result is proved for top-down tree transducers in general
in Section 4 of this paper (Corollary 4.7). Aho and Ullman also proved that
the exponential output size problem for generalised syntax-directed translations
is decidable [1, Theorem 4.3]. However, complexity issues are not addressed in
their paper, and the proposed algorithm is highly inefficient while the results in
this paper yield an NL-algorithm if formulated for generalised syntax-directed
translations (due to their close relationship with total deterministic top-down
tree transducers).
Bottom-up tree transducers are somewhat less interesting because their computations
are structurally simpler. By a polynomial-time reduction one can
exploit the results on total top-down tree transducers in order to show that the
exponential output size problem for bottom-up tree transducers is in P. In fact,
using known results it turns out that the problem is P-complete. Interestingly,
in this case the assumption of totality does not make a difference-the problem
remains P-complete even for total deterministic bottom-up tree transducers.
The paper is structured as follows. In the next section some basic notions
are recalled. Sections 3-5 are concerned with top-down tree transducers. In
Section 3 their definition is recalled, some auxiliary notions are introduced, and
it is shown that the exponential output size problem can be reduced to the case
of total deterministic top-down tree transducers with monadic input signatures.
In Section 4 a combinatorial result on trees is shown which can be used to
obtain a characterisation of exponential output size. The latter is turned into
decision algorithms in Section 5, where the main result of this paper is presented.
Section 6 deals with the complexity of the exponential output size problem for
bottom-up tree transducers. Finally, in Section 7 a short conclusion is given.
Preliminaries
The set of all natural numbers (including 0) is denoted by N, and N+ denotes
N nf0g. For n 2 N, [n] denotes the set ng. The set of all finite sequences
over a set A is denoted by A   . The empty sequence is denoted by -, the length
of a sequence s by jsj, and the concatenation of sequences by juxtaposition.
Like the length of a sequence, the cardinality of a set A is denoted by jAj. The
canonical extensions of a function f : A ! B to the powerset of A and to A
are denoted by f , too. Hence,
an an 2 A. The reflexive and transitive
closure of a binary relation r ' A \Theta B is denoted by r   . The domain of r, i.e.,
the set fa 2 A j (a; b) 2 r for some b 2 Bg, is denoted by dom(r).
It is assumed that the reader is familiar with the basic notions of complexity
theory and has at least some basic experience concerning the estimation of
resources needed by an algorithm (especially with respect to polynomial and
exponential time and logarithmic space). A function f : N ! N is said to be
polynomially bounded if there is a polynomial p such that f(n) - p(n) for all
N. If there are constants c 2 R, c ? 1, and n 0 2 N such that f(n) - c n for
all is said to be exponential. Thus, the latter is a lower bound
whereas the former is an upper one!
A (finite, ordered) unlabelled tree is a finite prefix-closed subset T of N
. The
elements of T are called its nodes. The rank of a node v in T is the number of
distinct . The rank of T is the maximum rank of its
nodes. A leaf is a node of rank 0. A node u is a descendant of a node v if v is a
proper prefix of u. Conversely, u is a ancestor of v if it is a proper prefix of v.
The subtree of T rooted at v is the tree fv 0 j vv 0 2 Tg. A direct subtree of T is a
subtree of T rooted at v for some . The size of T is jT j, its height is
(i.e., the number of nodes on a longest path from
the root to a leaf), and its width, denoted by wd(T ), is the number of leaves in
T .
A labelled tree is a mapping is an unlabelled tree and L
is a set of labels. The underlying unlabelled tree T is also denoted by N (t)
in this case. All notions and notations introduced for unlabelled trees above
carry over to labelled trees in the obvious way. In the following, the attributes
'labelled' and `unlabelled' will mostly be dropped when speaking about trees.
As a general rule, unlabelled trees will be denoted by capital letters (usually T )
whereas labelled trees will be denoted by lowercase letters (usually s and t).
For trees denotes the tree t such that
usually denoted by f (which actually
means that we identify a single-node tree with the label of that node).
A symbol is a pair (f; n) consisting of a label f and a number n 2 N, called the
rank of the symbol. Such a symbol is also denoted by f (n) , or simply f if n is
of minor importance. A signature is a finite set \Sigma of symbols. \Sigma is monadic if
for some signature \Sigma 0 all of whose symbols are of rank 1. For an
arbitrary set S, mon(S) denotes the monadic signature ff (1) g.
A tree is called monadic if it has the form f 1
Note that such a monadic tree can be identified with the string f 1
For a signature \Sigma and a set S of trees, \Sigma(S) denotes the set of all trees
the set of trees over \Sigma with subtrees in S. It is the smallest set of trees such that
The notation T \Sigma is used as an abbreviation for T \Sigma (;).
For the rest of this paper, let us fix an indexed set of pair-wise
distinct symbols of rank 0 called variables. For every n 2 N,
g. In order to avoid confusion, the set X is assumed to be disjoint
with all signatures under consideration. The variable x 1 is also denoted by x.
For trees t; t denotes the
substitution of t i for x i in t (i 2 [n]). More precisely, if
then then
rewriting works as usual, except that only left-linear rules are considered.
Thus, in the context of this paper a rewrite rule is a pair ae = (l; r) of trees, called
the left- and right-hand side, respectively, such that l contains every variable at
most once and every variable in r occurs in l, too. Such a rewrite rule is usually
denoted by l ! r. The derivation relation determined by ae is the binary relation
ae on trees such that s
exactly once, and R is a set of
rewrite rules, !R denotes the union of all ! ae with ae 2 R.
3 Top-down tree transducers
Top-down tree transducers transform input trees into output trees in a top-down
manner, using a restricted type of term rewrite rules. Special symbols of rank 1
are used as states which, in every step, consume the input symbol beneath and
replace it by a tree consisting of output symbols and states processing copies of
the direct subtrees of the consumed symbol.
3.1 Definition (top-down tree transducer) A top-down tree transducer is a
tuple
ffl \Sigma and \Sigma 0 are signatures, called the input signature and the output signature,
respectively,
is a signature of states of rank 1 each, disjoint with \Sigma [ \Sigma 0 ,
is a finite set of rewrite rules, and
is the initial state.
If \Sigma is a monadic signature, then td is a (top-down) string-to-tree transducer.
The top-down tree transduction computed by td , which is denoted by td as well,
is the set of all pairs (s;
such that
td t, where ! td denotes
the rewrite relation !R . \Pi
In the following, for every top-down tree transducer
every state fl 2 \Gamma, the top-down tree transducer (\Sigma; \Sigma 0 ; \Gamma; R; fl) is denoted by
td fl . As a convention, it is assumed that the variables in the left-hand side of a
rule, read from left to right, are always x N. Thus, every
rule of a top-down tree transducer has the form
where fl; From now
on, denoting a rule in this way is always meant to imply that t is chosen in such
a way as to contain every variable in X l exactly once. This carries over to the
denotation of derivation steps: in fl[f
every
is assumed to correspond to one particular occurrence of this subtree in
(but notice that we may have
for distinct
of course).
A rule of a top-down tree transducer is called a flf -rule if it has the form
t. Thus, a flf -rule is a rule that processes the input symbol
f in state fl. A top-down tree transducer
contains at least one flf -rule for every
it contains at most one such rule for every
total then dom(td) = T \Sigma , and if it is deterministic then it computes a partial
function. In the latter case one may therefore use functional notation, writing
3.2 Definition (output size) The output size of a top-down tree transducer
td is given by the function os td : N ! N such that, for all n 2 N,
ng
(where, as usual,
The exponential output size problem is the problem to determine, for an arbitrary
top-down tree transducer td , whether os td is exponential. \Pi
Note the technically convenient fact that os td is a monotonic function. Clearly,
one can always find some c such that os td (n) - c n for all n 2 N. This follows
from the fact that the rank of output trees is bounded and (s; t) 2 td implies
is the maximum height of right-hand sides of rules of
td .
The remainder of this section consists of three lemmas and their proofs. The
purpose of these lemmas is to show that a top-down tree transducer can be simplified
in a certain way without affecting the output size too much. In particular,
the modifications preserve polynomial boundedness as well as exponentiality.
The first lemma shows that it suffices to consider top-down tree transducers
whose right-hand sides contain exactly one output symbol each. For this, let \Theta
denote the set of all top-down tree transducers (\Sigma; H; \Gamma; R; fl 0 ) such that every
right-hand side of a rule in R is an element of H (\Gamma(X
for some m 2 N. Thus, standard output symbols h (n) are used, where n may
vary but the label is always h. This "overloading" of h is not essential, but it
helps reduce the notational complexity of proofs. Clearly, this standardisation
is harmless since the size of output trees is independent of their node labels.
3.3 Lemma For every top-down tree transducer td one can construct a top-down
tree transducer td 0 2 \Theta such that, for some constant a 2 N+ ,
for all n 2 N. The construction preserves determinism as well as totality, and
can be carried out on logarithmic space.
Proof. Let
lows. For every rule fl[f [x
in R, let R 0 contain
the rule fl[f [x
]], and let H consist of all symbols
h (l) which appear in the so-defined right-hand sides. Clearly, this construction
can be carried out on logarithmic space and it preserves determinism and
totality.
It remains to estimate the difference between os td and os td 0 . Let a be the
maximum number of nodes in right-hand sides of rules in R which are labelled
with symbols in \Sigma 0 . By the obvious one-to-one correspondence between derivations
in td and td 0 , and the fact that every application of a rule in R 0 adds
exactly one output symbol while the corresponding rule in R adds at most a,
Consequently,
(n) for all n 2 N.
Conversely, for every (s; t 0 there is some (s; t) 2 td such that wd(t 0
wd(t). (Notice that the same does not necessarily hold with respect to size because
some rules in R may have right-hand sides in \Gamma(X ).) Using this inequality
and the fact that ht(t 0
In other words, os td 0 (n) - n \Delta os td (n) for all n 2 N.
The next two lemmas are quite useful in order to check for an exponential
output size as they allow to restrict one's attention to the case of deterministic
total string-to-tree transducers, which are considerably easier to deal with than
general top-down tree transducers. In particular, some of the constructions used
in the following (see, e.g., the proof of Lemma 3.5) rely on the assumption that
every state of the given top-down tree transducer determines a partial function
from trees to trees. Therefore, we shall first show that logarithmic space is
sufficient in order to transform a top-down tree transducer into a deterministic
one, thereby affecting its output size only modestly. To simplify the proof, only
top-down tree transducers in \Theta are considered. By Lemma 3.3 (and the fact
that logarithmic space reductions are closed under composition) this restriction
does not make a difference.
Let us first informally discuss the idea underlying the construction. To get
rid of the nondeterminism (while preserving the output size), a modified input
signature is used. Intuitively, the nodes of an input tree are augmented with
additional information which determines the rules to be applied. Proceeding in
f
f
f
e e!

Figure

1: A sample derivation of a nondeterministic top-down tree transducer.
this way, some potential output trees may get lost since the new transducer is
forced to use the same rules whenever it processes two copies of a subtree in the
same state. Fortunately, this does not matter with respect to output size, as it
does not affect the maximal size of output trees.
As an example, let consists of the
rules ae
duplicates the ith subtree of the tree it is applied to and deletes the other one.
A sample derivation (applying rules in parallel) is shown in Figure 1. Note that,
in the second step, different rules have been chosen to process the copies of the
tree f [f [e; e]; e]: the left one is processed by ae 2 and the right one by ae 1 . To
obtain an output tree of maximal size, ae 1 would have to be chosen for both
copies.
In order to convert td into a deterministic top-down tree transducer td 0 , one
may use two versions of f , say f 1 and f 2 . This accounts for the fact that we
have to choose between two possible flf -rules. The rules are thus turned into
there is
only one fle-rule, it can be kept as is. Note that we cannot provide the input
tree in Figure 1 with appropriate indices in order to make td 0 simulate the shown
derivation, because of the contradictory choice of rules in the second step. How-
ever, it is possible to find indices which lead to an output tree of maximal size,
namely (where the dashes indicate irrelevant indices).
Generalising the construction, every symbol of the original input signature \Sigma
would have to be provided with as many indices as there are states in td , because
the choice of rules for copies being processed in different states must of course be
independent of each other. Unfortunately, this would result in an exponential
number of states, which could not be handled on logarithmic space. Therefore,
instead of indices we shall use additional input symbols hfl; ii of rank 1, where
fl is a state of td and i is the index of a rule. Intuitively, an occurrence of hfl; ii
in the input tree may be read: "If fl is the current state, use the i-th flf -rule of
td in order to process the next input symbol f 2 \Sigma that will be encountered."
In order to remember i, states of the form fl i will be used.
3.4 Lemma For every top-down tree transducer td 2 \Theta one can construct a
deterministic top-down tree transducer td 0 2 \Theta such that, for some constant
a 2 N+ ,
for all n 2 N. The construction preserves totality and can be carried out on
logarithmic space.
Proof. Let define m to be the largest natural number
such that, for some are m distinct flf -rules in R.
(with
For all contains the rule fl i [hfl;
as, for all fflg, the rule In order to define R 1 ,
consider some such that R contains at least one flf -rule.
Let
be an arbitrary order on the set of all flf -rules in R. Then R 1 contains the rules
The rules for which have the same right-hand side as the one for
are needed in order to preserve totality. The choice of the superscript 1
for all states in the right-hand sides is arbitrary; it could be replaced with any
other
It should be clear that td 0 can be constructed on logarithmic space, since this
requires mainly the manipulation of a fixed number of counters ranging over
[m]. Furthermore, td 0 is deterministic and the construction preserves totality.
Moreover, for every (s; t) 2 td 0 , removing the symbols of the form hfl; ii from
s yields a tree s 0 such that (s This proves that os td 0 (n) - os td (n)
for all n 2 N. In order to see that the other inequality holds as well, one has
to cope with the difficulty discussed above, namely that some of the possible
derivations of td have no counterpart in td 0 since the latter will always apply
the same rules when copies of a subtree are processed in the same state. The
proof proceeds by explicitly turning an arbitrary input tree for td into one for
td 0 which yields an output tree of maximal size.
For every tree s 2 T \Sigma and every choose an arbitrary but fixed derivation
td s 0 with s 0 2 TH such that js 0 j is maximal, and let i(s; if the
first rule applied in this derivation is the j-th flf -rule in R (with respect to the
order used to define R 1 is the root symbol of s. If there is
no derivation
can be chosen arbitrarily.
(Recall the informal discussion preceding the lemma: i(s; fl) is the index of
the rule which must be applied to fl[s] in order to obtain an output tree of
maximum size.) Now, suppose and define for every tree
Clearly, Therefore, defining a
have established the required inequality os td (n=a) - os td 0 (n) once the following
claim is proved.
Claim. Let fl[s] !
td t for some . Then there is a
derivation
To prove the claim, proceed by induction on the structure of s. Suppose
Due to the definition of i(s; fl) we can assume without loss of
generality that the rule applied in the first step of the derivation fl[s] !
td t is
the i(s; fl)-th flf -rule of td . Thus, if the given derivation has the form
applying the induction hypothesis to the subderivations
trees t 0
l 2 TH such that
es k
l [es i l
td
l
for all j 2 [l], which proves the claim (by taking t
l ]) and thus
finishes the proof of the lemma.
Intuitively, if a derivation of a top-down tree transducer produces a large output
tree, there must be a path in its input tree whose nodes are copied an exponential
number of times. Thus, if we turn a top-down tree transducer td into a string-
to-tree transducer st which interprets its input as a path in an input tree of
td and simulates the corresponding part of the derivation, the output size of st
should not differ from the output size of td very much. The following lemma
proves that this is indeed the case.
Lemma For every deterministic top-down tree transducer td 2 \Theta one can
construct a total deterministic string-to-tree transducer st 2 \Theta such that, for
some constant a 2 N,
st (n) - max(1; os td (a \Delta n))
for all n 2 N. The construction can be carried out on logarithmic space if td is
total, and in exponential time otherwise.
Proof. Let As indicated above, the main idea is to
construct st in such a way that an input tree of st corresponds to a path in
an input tree of td . A computation of st on such a path produces the output
tree which consists of all nodes td produces by processing symbols on this path.
technical reasons, the leaf f (0) at the end of a path will not be taken into
account; it is treated as ffl.) In order to cope with the possible non-totality of
td , the states are enriched by a second component which is a set of states and is
used in order to keep track of all states in which copies of the remaining input
are being processed. To make this precise, some auxiliary definitions turn out
to be useful.
For every f (k) 2 \Sigma, denote by lstates(f) the set of all states
the flf -rule in R exists. Furthermore, for
rstates denote the set of all states
of the right-hand side of some flf -rule for which fl 2 \Delta. Intuitively, if \Delta is
the set of states processing copies of a tree f [s after a simultaneous
derivation step rstates \Delta (f; i) will be the set of states processing copies of s i .
Finally, for every set of states \Delta ' \Gamma, let
dom
st
constructed as follows.
Consider some hfl; \Deltai suppose
dom(rstates
In this case, if fl[f [x
is the flf -rule in R, then
R 0 contains the rule
where
(Note that the h in the original flf -rule has rank l, whereas the new one has
rank p.) Otherwise (i.e., if it is not the case that (1) and (2) hold), R 0 contains
the rule hfl; \Deltai[f i Furthermore, the rule hfl; \Deltai[ffl] !h is in R 0 for every
state hfl; \Deltai
By construction, st is total and deterministic. In order to show that the stated
inequalities hold, two claims are proved. The first claim concerns the inequality
os st (n) - max(1; os td (a \Delta n)).
Claim 1. There is a constant a 2 N such that the following holds for every
state hfl; \Deltai ;. For every derivation hfl; \Deltai[s] !
st t (where
there is a tree s depending only on s and \Delta,
such that js 0 j - a \Delta jsj and fl[s 0
To prove is the maximum rank of symbols
in \Sigma and a 0 is the smallest positive natural number such that every nonempty
3 Recall that all symbols f (0) 2 \Sigma are treated as ffl in st. Therefore, only f i
for f of rank
need to appear in S.
set dom contains a tree of size at most a 0 . (Notice that a 0
exists because the powerset of \Gamma is finite.) Let us proceed by induction on the
length of derivations. The claim certainly holds if the considered derivation has
the form hfl; \Deltai[s] ! st h, choosing as s 0 a smallest tree in dom (\Delta). Now, assume
that the derivation hfl; \Deltai[s] !
st t reads
st h[hfl
st
where the rule applied in the first step is the one constructed from a rule
in R as described in the definition of R 0 .
k ] be the tree whose subtrees s 0
are defined as fol-
lows. For
j is a smallest tree in dom(rstates \Delta (f; j)) (which, by the
construction of R 0 , is a nonempty set). Furthermore, s 0
i is the tree (provided
by the induction hypothesis) of size - a \Delta js i j for which there are derivations
p such that t 0
(Notice that the induction hypothesis yields the same input tree s 0
all p derivations because s 0
depends only on s i and \Delta i .) It follows that
and
td
td
is a tree containing in particular the subtrees t 0
p , which
means
This finishes the proof of Claim 1. The claim yields os st (n) - os td (a \Delta n) for all
every tree s 2 T mon(S) , which means that os st
To formulate the second claim, it is convenient to formalise the notion of paths
through a tree s 2 T \Sigma . For this, define paths(s) 2 T mon(S) as follows. For
2. Let hfl; \Deltai dom (\Delta). For every tree t 2 TH with
td t it holds that
Again, the proof is by induction on the length of derivations. For derivations
of length 1 we have so the assertion trivially holds. Now,
assume that the given derivation has the form
td
td
where l - 1. First of all, notice that s i 2 dom This is
because, by assumption, s 2 dom (\Delta) and, by definition, \Delta i is the set of all
states occurs in s 0 for some fl 0 2 \Delta, where s 0 is the
unique tree such that
for one such state
would mean that there did not exist a derivation
0 with
thus violating the assumption s 2 dom(td fl ).
The fact that s i 2 dom implies (2) in the definition of R 0 ,
and (1) is obviously satisfied as well. Consequently, if I
then the derivation step
st
exists and, by the induction hypothesis,
for all j 2 I i . Summing up, we get
(st
as claimed.
By choosing
there is a path s 0 2 paths(s) such that wd(st(s 0 wd(t)=wd(s). This is due to
the fact that
This proves the inequality os td (n)=n 2 - os st (n) for all n 2 N since
How much time does it take to construct st? Clearly, the most time consuming
part is to determine the set (which is necessary
in order to construct the rules). This can be done by a standard algorithm,
as follows. Define be the set of all
such that there exists an input symbol f (k) 2 \Sigma for which \Delta ' lstates(f) and
rstates \Delta (f; time is sufficient in order
to determine D i+1 since we can just enumerate the 2 j\Gammaj sets test for
each of them whether it satisfies the requirement. It follows by straightforward
inductions that
i2N D i . Furthermore, by definition D i ' D i+1 for all
, where
is the smallest index such that D i 0
this shows that D is computable in exponential time.
This completes the proof for the general case. It remains to consider the special
case where td is total. Totality of td means that dom
Therefore, in the construction of rules conditions (1) and (2) are always satisfied,
regardless of \Delta. As a consequence, the second component of a state in \Gamma 0 is
useless and one can simplify the construction:
is the
set of all rules fl[f i

Figure

2: A tree of branching depth 2 and branching index 3.
I i is as in the proof of Claim 2 and these rules can be
computed on logarithmic space, which completes the proof of the lemma.
The reader should notice that the inequalities in the three lemmas above guarantee
that polynomial boundedness and exponentiality are preserved. With
respect to polynomial boundedness this is clear because the upper bounds are
obviously polynomials if os td is one. Exponentiality is preserved as well. For
os td (n=a), where a is a constant, this is clear because c
For os td (n)=p(n), where p is a polynomial, choose
order to get c n which is exponential because the second
factor is larger than 1 for sufficiently large n (since d ? 1).
4 The branching index of output trees
In this section it will be shown that, intuitively, a tree whose size is exponential
in its height must necessarily contain a subtree with many ramifications on every
path. In order to formalise this, the branching depth and the branching index
of trees are introduced.
4.1 Definition (branching depth and branching index) Let T be a tree. The
branching depth of T is the smallest natural number b such that there is a leaf
which has exactly b distinct ancestors of rank - 2. The branching index
of T is the maximum branching depth of all trees T 0 ' T . \Pi
An example is shown in Figure 2. The branching depth of the tree is 2 while
the branching depth of the subtree indicated by hollow edges is 3. The latter
turns out to be the branching index of the tree as a whole because there is no
subtree with a larger branching depth. The reader should notice that every tree
T contains a tree T 0 ' T of rank - 2 which has the same branching depth b
as T . Therefore, the tree T 0 in Definition 4.1 can be assumed to have at most
the rank 2, without loss of generality. It may furthermore be instructive to
note that one could remove all nodes which have more than b pairwise distinct
ancestors of rank 2, yielding a tree in which all leaves have exactly b ancestors
of rank 2. Intuitively, this turns the tree into a full binary tree of height b
if nodes of rank 1 are disregarded. Hence, the branching index of T is one less
than the height of the largest full binary tree which can be "embedded" in T .
The following lemma yields an equivalent recursive description of the branching
index. The straightforward inductive proof is omitted.
4.2 Lemma Let T be a tree with direct subtrees T . The branching
index of T is 0 if
the branching index of T i . Then the branching index of T is there are
distinct and it is b if such indices do not exist. \Pi
The lemma below states that the size of trees is polynomially bounded in their
height if we place an upper bound on their branching index (provided that the
rank is bounded).
4.3 Lemma Let S be the set of trees of rank - r and branching index - b, for
some N. There is a polynomial p b of degree b+1 such that jT j - p b (ht(T
for all trees T 2 S.
Proof. Proceed by induction on b. A tree T of branching index 0 can at
most be of rank 1, which implies jT
let T be a tree of branching index - b having k - r direct subtrees T
If the branching index of one of T was greater than b or there were
distinct such that the branching index of both T i and T j is b, then
the branching index of T would be at least b Therefore,
at most one of the direct subtrees (T 1 , say) is of branching index b, all the
remaining ones having a strictly smaller branching index. According to the
induction hypothesis, T
polynomial p b\Gamma1 of degree b (since the coefficients of p b\Gamma1 can be assumed to
be positive). Therefore, jT Repeating the
argument for T 1 until a tree of size 1 is reached, yields
which is a polynomial in ht(T ) of degree b is one of degree b.
As a corollary, the branching index cannot be bounded if the size of the trees
in a set grows exponentially in their height.
4.4 Corollary Let S be a set of trees of bounded rank, and let size S
ng for all n 2 N. If size S is not polynomially bounded,
then then there is no upper bound on the branching index of trees in S. \Pi
Let us say that a tree t contains a bifurcation if there is a node v 0 2 N(t)
with two distinct descendants v 0 v;
The next lemma states that in every set of labelled trees (with
finitely many labels) of unbounded branching index there is a tree containing
a bifurcation. This will be used in the proof of Theorem 4.6 in order to create
a kind of pumping situation which characterises string-to-tree transducers of
exponential output size.
Lemma Let S be a set of trees with labels in a finite set L. If the
branching index of trees in S is unbounded, then there exist a tree t 2 S
containing a bifurcation.
Proof. For denote the set of labels on the path to
g. We mainly have to prove
the following claim, which is done by induction on n.
Claim. Let t 2 S and n 2 N, and let T ' N(t) be a tree of branching depth
does not contain distinct nodes v 0 v; v 0 v 0 which satisfy
there is a node w 2 T such that
For this is trivial, taking as w any node in T . Therefore, let n - 1 and
assume that the claim holds for trees T 0 ' N(t) of branching depth B(n \Gamma 1).
As pointed out after Definition 4.1, it may be assumed without loss of generality
that the rank of T is 2. Consider the tree T 0 ' T which consists of all nodes
having at most B(n \Gamma 1) ancestors of rank 2. Thus, the branching depth
of T 0 is 1). By the induction hypothesis this implies
some node v 0 2 T 0 . There is nothing to show if
that
choose a leaf v 0 u 2 T such that juj is minimal. Since v 0 has at
most ancestors of rank 2 in T whereas v 0 u has at least B(n) (since
this is the branching depth of T ), there are at least n ancestors v 0 u 1 of v 0 u
whose rank is 2. By the minimality assumption on juj this means that the set
jujg has at least n+1 elements. By assumption, no label in
twice among the labels of nodes in N . This implies the existence
of a node v 0 v 2 N such that t(v 0 v) 62 t(v 0 ), and thus completes the proof of the
claim since it means that
Now, in order to prove the lemma, choose a tree t 2 S of branching index at least
B(jLj). Then there is a tree T ' N(t) of branching depth B(jLj). However,
since there cannot be a node w 2 T such that t(w) ? jLj, it follows from the
claim that T contains a bifurcation.
The decision algorithm to be developed in the next section is based on a theorem,
to be proved next, which characterises the class of total deterministic string-to-
tree transducers st 2 \Theta of exponential output size. In fact, the theorem could be
generalised to arbitrary top-down tree transducers, but this would be technically
more difficult and is not needed to prove the results of this paper. In order to formulate
the theorem (and for further use as well), the notion of computation trees
is needed. Intuitively, the computation tree of a derivation is the tree of states in
which copies of subtrees of the input tree are processed. We only need this definition
for string-to-tree transducers in \Theta. Therefore, let st = (\Sigma; H; \Gamma; R;
The computation tree of a derivation fl[s] !
st t with
is the tree with labels in \Gamma which is defined as follows. If the derivation has the
st h then its computation tree is the tree fl. Otherwise, the derivation
must have the form fl[f [s 0 st
st In this
case, its computation tree is fl[t 0
i is the computation tree of
the i-th subderivation
st [k]. The set of all computation trees
of derivations
st t with s 2 T \Sigma and t 2 TH is denoted by ct(st).
4.6 Theorem The output size of a total deterministic string-to-tree transducer
st 2 \Theta is exponential if and only if there is a tree in ct(st) containing a
bifurcation.
Proof. Let st = (\Sigma; H; \Gamma; R; fl 0 ). For the proof, notice that the computation
tree ct of a derivation fl[s] !
st t has the same structure as t, i.e.,
Thus, it makes no difference whether we consider the size of output trees or the
size of computation trees.
Due to the remark above, and by the fact that for the
computation tree ct of a derivation fl[s] !
st t, we have size ct(st) (n) - os st (n)
for all n 2 N (where size ct(st) is defined as in Corollary 4.4). By Corollary 4.4
this means that the branching index of trees in ct(st) is unbounded. Thus, the
implication follows from Lemma 4.5.
Consider some derivation
st t whose computation tree ct contains
nodes of the required type. Then one can decompose s into
ct i be the computation tree of the (unique) derivation
st
, where By induction on i it follows
that jct i this is trivial. For i ? 0, since ct(v 0
there is a derivation fl[s i
st s,
where s is a tree containing at least two subtrees of the form fl[s
As
a consequence, the computation tree ct i of the derivation fl[s i
st
st t i
contains ct twice as a subtree, which proves jct
The fact that ct(v 0 implies the existence of a derivation
st s, where s is a tree containing the subtree fl[s i
quently, the computation tree of the derivation
st
st t 0
i with
contains ct i as a subtree, which means that its size is at least 2 i . For
st
which is exponential because 2 \Gammam 0 is a constant factor and 2 1=m1 ? 1. (Note
that 1=m 1 is defined as m
As a by-product of the results in this section a result similar to Theorem 5.2 of [1]
is obtained: If the output size of a top-down tree transducer is not exponential,
then it is polynomially bounded. (In fact, the result in [1] is slightly stronger
as it states that, in this case, the output size satisfies c 1
for some c 1 In other words, it cannot be an element of
4.7 Corollary The output size of a top-down tree transducer is either polynomially
bounded or exponential.
Proof. Let td be a top-down tree transducer. By Lemmas 3.3, 3.4, and 3.5
there is a total deterministic string-to-tree transducer st 2 \Theta, such that os st is
polynomially bounded (exponential) if and only if td is polynomially bounded
(respectively exponential). If os st is not polynomially bounded, the only-if
direction of the proof of Theorem 4.6 remains valid. This shows that there is
a computation tree in ct(st) containing a bifurcation. Using the if direction
of the theorem it follows that os st is exponential, which means that os td is
exponential.
5 The main result
In this section the main result of the paper is proved: The exponential output
size problem is NL-complete for total top-down tree transducers and DEXP-
TIME-complete in the general case. First, it is shown that there are decision
algorithms which obey these resource bounds, starting with the total case.
5.1 Lemma For total deterministic string-to-tree transducers in \Theta, the exponential
output size problem is in NL.
Proof. By Theorem 4.6 it suffices to prove the following.
For a total deterministic string-to-tree transducer st 2 \Theta it can be
decided by a nondeterministic Turing machine on logarithmic space
whether there is a computation tree in ct(st) containing a bifurcation.
To sketch how such a Turing machine M could work, let st
For every state fl 2 \Gamma and every input symbol f (1) 2 \Sigma, let next(fl; f) denote
the set of all states which occur in the right-hand side of the unique flf -rule in
R. A computation of M consists of two phases. In the first phase, starting with
repeatedly makes nondeterministic choices to "guess" the next symbol
f (1)
of an arbitrary input string, and a state fl i+1 2 next(fl
is the initial state of st). Thus, fl 0 is the sequence of labels on a path in
the unique computation tree which is determined by the guessed input string
. During this phase of its computation, M nondeterministically selects
one of the encountered states (say
stores it on the tape.
At some step j 0 - i 0 , the next phase is initiated by guessing two states
which need not be distinct, but must correspond to two
distinct nodes in the right-hand side of the respective rule. (Formally, if t is
the right-hand side of the fl j0 f j0 -rule, then fl j0
distinct nodes v; Intuitively, this is the place
where the two paths of the bifurcation separate. From now on, two sequences
are constructed in parallel, always choosing
some f (1)
states
accepts st if it encounters some i ? j 0 such that
Since st is total, every derivation finally yields a tree in TH . Therefore, if M
accepts its input in step i, the computation tree ct of the derivation on input
exists. Obviously, the acceptance condition means that ct
contains a bifurcation. Conversely, if there exists an input tree leading to a
computation tree that contains a bifurcation, it is clear that one of the possible
runs of M will make suitable nondeterministic choices in order to detect this
fact. Moreover, M requires only logarithmic space since the only things it must
keep track of are
and the current symbols f i ,
i . This completes the
proof.
5.2 Theorem The exponential output size problem is NL-complete for total
top-down tree transducers and DEXPTIME-complete for general ones. Both
parts of the statement remain true if only deterministic top-down tree transducers
are considered.
Proof. Let td be a top-down tree transducer. By Lemmas 3.3-3.5 one can
construct a total deterministic string-to-tree transducer st 2 \Theta such that os st
is exponential if and only if os td is exponential. Furthermore, the construction
can be performed on logarithmic space if td is total and in exponential time
otherwise. Using Lemma 5.1 it can be tested on logarithmic space (in the size
of st) whether os st is exponential. Thus, the exponential output size problem
is in NL for total top-down tree transducers and in DEXPTIME in general. It
remains to prove NL-hardness and DEXPTIME-hardness, respectively.
In order to establish this for the total case, it is shown that the NL-complete
problem Reachability (see, e.g., [12]), also known as the graph accessibility
problem, can be reduced to the exponential output size problem for total top-down
tree transducers. Given a directed graph G and two nodes v; v 0 , Reachability
is the problem to determine whether there exists a vv 0 -path in G, i.e.,
a directed path leading from v to v 0 .
If V is the set of nodes of the input graph G to Reachability, let st =
g, and R
is defined as follows.
(1) For all u; u contains the rule fl u [u 0
[x] if there is an edge
from u to u 0 in G. If there is no such edge then R contains the rule
(2) For all nodes contains the rule fl u [ffl] ! ffl.
(3) In addition, R contains the rule
Clearly, a work tape of logarithmic size is sufficient for a Turing machine to
construct st . Furthermore, if G does not contain any vv 0 -path then the rule
in (3) will never be applied, so that Conversely,
if there is a vv 0 -path given by a sequence e 1
is the target node of e j for
By the rules in (1) and (3) there is a derivation
st
st
which means that st contains all pairs (s is a full binary tree of
height i. Consequently, os st ((k +1) \Delta proving that os st is exponential
(since k is a constant).
Finally, consider the general case. We are going to make use of a DEXPTIME-
completeness result by Seidl. A (deterministic top-down) finite tree automaton
is a deterministic top-down tree transducer ta = (\Sigma; \Sigma; \Gamma; R;
every flf -rule in R has the form fl[f [x
ously, the computed relation ta is a partial identity. Seidl [14] showed that it
is DEXPTIME-hard to decide whether dom(ta 1
tree automata ta ta n given as input. Let ta
assume without loss of generality that the sets of states are pairwise
disjoint. Now, let given by the following components
(where the symbols f; and the states are supposed to be new ones):
and R 0 contains the rules
Clearly, td is deterministic, and dom(ta 1 implies that
the computed tree transduction is empty. Otherwise, choose an arbitrary tree
be the tree
1. Then there is a derivation
where t i is a complete binary tree of height i +1 over f and ffl. Thus, the output
size of td is exponential, which completes the proof of the theorem.
By Corollary 4.7, the set of all top-down tree transducers whose output size is
polynomially bounded is the complement of those whose output size is expo-
nential. Because of the famous result by Immerman and Szelepsc'enyi [10, 15]
stating that NL is closed under complement (and the fact that the same holds
for deterministic classes like DEXPTIME anyway), the polynomial output size
problem (i.e., to determine whether os td is polynomially bounded) turns thus
out to be in NL respectively DEXPTIME.
5.3 Corollary The polynomial output size problem is in NL for total top-down
tree transducers and in DEXPTIME for general ones. \Pi
6 Bottom-up tree transducers
In this section the output size of bottom-up tree transducers is considered. By
mistake, it was claimed in the conclusion of [3] that the results of Section 5 were
true also for bottom-up tree transducers. In fact, this holds neither in the total
nor in the general case (assuming that NL 6= P 6= DEXPTIME). Bottom-up
tree transducers cannot copy subtrees and then process them individually in
different states because copying takes place after the copied subtree has been
processed. This results in a considerably easier emptiness problem, which makes
it possible to apply a construction similar to the one in the proof of Lemma 3.5,
but using only polynomial instead of exponential time. On the other hand, the
result of a bottom-up tree transduction may depend on deleted subtrees because,
like copying, deletion takes place after processing a subtree. This means that,
intuitively, the deletion of large subtrees can simulate the effect of non-totality
on the output size. As a consequence, the exponential output size problem for
bottom-up tree transducers does not become easier if restricted to total bottom-up
tree transducers. The main result of this section states that the problem is
P-complete in both cases.
Let us first recall the definition of bottom-up tree transducers.
6.1 Definition (bottom-up tree transducer) A bottom-up tree transducer is a
tuple
are as in the definition of top-down tree transducers,
is a finite set of rewrite rules, and
is the set of final states.
The bottom-up tree transduction computed by bu, which is denoted by bu as well,
is the set of all pairs (s;
bu fl[t] for some
bu denotes the rewrite relation !R . \Pi
As in the top-down case it is assumed without loss of generality that the variables
in the left-hand side of a rule, read from left to right, are always x
some appropriate k 2 N. Thus, every rule of a bottom-up tree transducer has
the form f [fl 1 [x 1
are states, t is a tree in T \Sigma 0
l ) for some l 2 N (containing every variable in X l
exactly once), and x
A bottom-up tree transducer as in the definition is deterministic if R contains
at most one rule whose right-hand side is f [fl 1 [x 1
and \Gamma. Similarly, bu is total if there is at least one rule
whose right-hand side is f [fl 1 [x 1
The output size of bu is given by the function os bu which is defined
exactly as in the case of top-down tree transducers. Similarly, the definition of
the exponential output size problem carries over to the bottom-up case in the
obvious way.
Call a state fl of a bottom-up tree transducer
there are trees s 2 T \Sigma and t 2 T \Sigma 0
such that s !
bu fl[t]. The following problem
called Usefulness will be used below.
Instance A bottom-up tree transducer and a state fl 2 \Gamma.
Question Is fl useful?
As stated in the following lemma, State Usefulness is P-complete. This
is a rather obvious reformulation of the fact that the emptiness problem for
context-free string languages is P-complete [11, Corollary 11], using the well-known
relationship between context-free grammars and finite tree automata on
the one hand, and finite tree automata and bottom-up tree transducers on the
other (cf. the definition of finite tree automata in the proof of Theorem 5.2).
For the sake of completeness, an explicit proof is nevertheless added below.
6.2 Lemma State Usefulness is P-complete. The same holds if the problem
is restricted to total deterministic bottom-up tree transducers whose output
signature is fffl (0) g.
Proof. The proof is similar to the proof of [11, Corollary 11]. Let bu =
\Gamma. In order to decide whether there are trees s 2 T \Sigma
and
such that s !
bu fl[t], just apply the following standard technique:
and compute S 0 (which can obviously be done in polynomial
time). Then it follows by a straightforward induction that fl is useful if
and only if
It remains to prove P-hardness of the restricted variant. By [11, Corollary 9]
the following problem is P-complete: For a finite set S, a binary operation \Delta on
S (given by a multiplication table), a subset S 0 of S, and an element a 2 S,
decide whether a is in the closure of S 0 under \Delta (i.e., whether a is an element
of the smallest superset S 0 of S 0 such that b \Delta c
In the obvious way, every tree s 2 T \Sigma can be seen as an expression over \Delta and
constants in S 0 . By construction, there is a derivation s !
bu fl b [ffl] if and only if
b is the value of this expression. In particular, fl a is useful if and only if a 2 S 0 ,
as required. Furthermore, bu can be computed on logarithmic space as it is easy
to convert a multiplication table for \Delta into R. This completes the proof.
Similar to the top-down case it is convenient to simplify a given bottom-up
tree transducer in such a way that each right-hand side contains exactly one
output symbol. For this, let \Theta 0 be the set of all bottom-up tree transducers
and every right-hand
side of a rule in R is an element of \Gamma(H (X)).
6.3 Lemma For every bottom-up tree transducer bu one can construct a
bottom-up tree transducer bu 0 2 \Theta 0 such that, for some constant a 2 N,
os bu (n)=a - os bu 0
for all n 2 N. The construction can be carried out on logarithmic space.
Proof. Simply replace every rule f [fl 1 [x 1
in R
with
]]. By the same arguments as in the
proof of Lemma 3.3 this satisfies the claimed inequalities. Furthermore, it can
obviously be done on logarithmic space.
We can now show how to turn a bottom-up tree transducer into a total (top-
string-to-tree transducer, using a construction similar to the one in the
proof of Lemma 3.5.
6.4 Lemma For every bottom-up tree transducer bu 2 \Theta 0 one can construct
a total string-to-tree transducer st 2 \Theta such that, for some constant a 2 N,
os bu (n)=n 2 - os st (n) - max(1; os bu (a \Delta n))
for all n 2 N. The construction can be carried out in polynomial time.
Proof. Let 6.2 the set of useful states can be
determined in polynomial time. Obviously, the remaining states and the rules in
which they appear can be deleted without affecting the computed transduction.
Therefore, in the following we can assume without loss of generality that \Gamma
contains only useful states. Based on this assumption, let st = (mon (\Sigma);
is a new state and R defined as follows.
(1) For every rule f [fl 1 [x 1
in R and every i 2 [k],
contains the rule fl[f is the number of
times x i occurs among x
. If, for some does
not contain any rule of the form f [fl 1 [x 1
then R 1 contains the rule fl[f [x]] !h (in order to account for totality).
(2) For every rule fl[f contains the rule fl 0 [f
and the rule fl 0 [f
gg.
The remainder of the proof is a simplified variant of the reasoning in the proof
of Lemma 3.5.
Claim 1. There is a constant a 2 N such that the following holds for every state
. For every derivation fl[s] !
st t (where t 2 TH )
there is a tree s
bu
For the proof, let a 0 be the smallest natural number such that, for every
there is a tree s of size at most a 0 such that s
bu fl[t] for a tree t 2 TH .
Now define a is the maximum rank of symbols in \Sigma.
We proceed by induction on the length of derivations. If fl[s] ! st t then h, so
the claim holds with s . For the inductive step, let
a derivation
st
st
be such that jt jg. By the induction
hypothesis, there exists a tree s 0
bu
i is a tree in TH which satisfies jt 0
jg. By
construction, R contains a rule f [fl 1 [x 1
such that
times among x
. Define s
for all j 2 [k] n fig. A computation similar to the corresponding one in the
proof of Lemma 3.5 verifies the inequality js 0 j - a \Delta jsj. Furthermore, there is a
derivation
bu
bu
occurs p times among t 0
. For
we thus get
as claimed.
For the second claim let, for every tree s 2 T \Sigma , paths(s) ' T mon (\Sigma) be defined
as follows. For
)g. Furthermore, for every state
every tree s an arbitrary but fixed tree t 0 2 TH of
maximum width such that fl[s 0
st t 0 . (Notice that such a tree exists because
st is total.)
2. For every derivation s !
bu fl[t], where
holds that
Again, the proof is by induction on the length of derivations. For derivations
of length 1 the assertion is trivial as in this case
and consider a derivation
s
bu
bu
assuming that
tion, if i occurs p i times among contains the rule
fl[f Consequently, wd(- fl (f [s 0
for all s 0
in particular), which yields
as claimed.
Claims 1 and 2 prove the inequalities in the lemma, which can be seen as follows.
By the rules in R 2 , (s; st yields
st t for some state
Using Claim 1, the latter implies the existence of a pair (s bu such that
jtj. Thus, we have os st st (n) - os bu (a \Delta n),
which proves that os st (n) - max(1; os bu (a \Delta n)). For the other inequality, as
in the proof of Lemma 3.5, for all (s; implies the existence
of a pair (s st such that s As
shows that os bu (n)=n 2 - os st (n) for all n 2 N.
It is now easy to prove the main result of this section.
6.5 Theorem The exponential output size problem for bottom-up tree transducers
is P-complete. The same holds for total deterministic bottom-up tree
transducers.
Proof. By Lemma 6.3, Lemma 6.4, and Theorem 5.2 the exponential output
size problem for bottom-up tree transducers is in P. It remains to prove P-
hardness for the total deterministic case. This is done by reducing the problem
State Usefulness to the exponential output size problem for this class of tree
transducers.
By Lemma 6.2 it suffices to consider a total deterministic bottom-up tree transducer
\Gamma) and a state fl 2 \Gamma. We have to show how to
construct on logarithmic space a total deterministic bottom-up tree transducer
bu 0 such that os bu 0
is exponential if and only if fl is a useful state of bu. For
this, let bu and
Clearly, bu 0 is total and deterministic, and the construction can be performed
on logarithmic space. In order to verify the required equivalence, let s !
bu fl[ffl]
for some s 2 T \Sigma and define f
there is a derivation f
bu 0
bu 0
fl[t] for every i 2 N, where t is a
full binary tree over g and ffl of height i + 1. Thus, the output size of bu 0 is
exponential.
Conversely, if fl is not useful in bu, it is clear that the rule f
never be applied in a derivation s !
bu 0
Therefore,
for all such derivations it holds that is the only output symbol which
occurs in the remaining rules). Thus, os bu 0 is not exponential, which finishes
the proof.
Using Lemmas 6.3 and 6.4, Corollary 4.7 extends to bottom-up tree transducers.
Thus, since P is closed under complement, a corollary similar to Corollary 5.3
is obtained.
6.6 Corollary The polynomial output size problem for bottom-up tree transducers
is in P. \Pi
7 Conclusion
It was shown in this paper that the exponential output size problem is NL-
complete for total top-down tree transducers, DEXPTIME-complete for general
ones, and P-complete for bottom-up tree transducers. Intuitively, the reason
for the huge complexity gap between the two top-down variants is that, in the
general case, solving the problem requires to solve the emptiness problem for
top-down tree transductions.
There are several directions for future research which could be interesting. The
complexity of the exponential output size problem for compositions of top-down
or bottom-up tree transductions, or for more general classes of tree transducers
(like, e.g., macro tree transducers [7]) seems to be an interesting open problem.
Another point is that, as mentioned in the introduction, for every k 2 N one
can construct top-down tree transductions whose output size is bounded from
above by a polynomial of degree k (but not by a polynomial of degree k \Gamma 1).
In fact, by Corollary 4.7 the output size of a top-down tree transducer is either
bounded by a polynomial or exponential. For macro tree transducers, Engelfriet
and Maneth [6] showed that it is decidable whether the output size is linearly
bounded. Thus, it may be interesting to search for efficient algorithms which
determine, for a given top-down or even macro tree transducer - , the smallest
natural number k such that os - 2 O(n k ) (provided that such a k exists). Finally,
are there natural classes of non-total top-down tree transducers for which the
exponential output size problem is at least solvable on polynomial space?

Acknowledgement

I thank Joost Engelfriet, who told me where to find the
completeness results in [11] and pointed out the related work in [1], as well
as Helmut Seidl and an anonymous referee for their careful reading of the
manuscript and helpful lists of suggested improvements.



--R

Translations on a context free

The complexity of the exponential output size problem for top-down tree transducers
Some open questions and recent results on tree transducers and tree languages.
Three hierarchies of transducers.
Characterizing and deciding MSO- definability of macro tree transductions
Macro tree transducers.
Zolt'an F-ul-op and
Tree languages.
Nondeterministic space is closed under complement.
Complete problems for deterministic polynomial time.
Computational Complexity.
Mathematical Systems Theory
Haskell overloading is DEXPTIME-complete
The method of forced enumeration for nondeterministic automata.
Generalized 2 sequential machine maps.
There's a lot more to finite automata theory than you would have thought.
Tree automata: an informal survey.
--TR
The method of forced enumeration for nondeterministic automata
Nondeterministic space is closed under complementation
Haskell overloading is DEXPTIME-complete
Tree languages
Syntax-Directed Semantics
Characterizing and Deciding MSO-Definability of Macro Tree Transductions
Exponential Output Size of Top-Down Tree Transducers

--CTR
Frank Drewes , Joost Engelfriet, Branching synchronization grammars with nested tables, Journal of Computer and System Sciences, v.68 n.3, p.611-656, May 2004
complexity;tree transducer;output size;completeness