It’s a Small Inverse
Kazuhiro Inaba (kinaba@nii.ac.jp)
September 10, 2010

1

Existence of Linear-Size Inverse

We assume the reader to be very familiar with the theory of tree transducers [Eng77, Bak79, EV85]. The
goal of this note is the following theorem.
Theorem 1.1. Let f ∈ Dt MTT∗ , i.e., f is a tree-to-tree function that can be expressed by a finite compositionof total deterministic macro tree transducers. Then,()∃c ∈ N. ∀t ∈ range(f ). ∃s ∈ dom(f ). f (s) = t ∧ |s| ≤ c|t|where |s| and |t| denotes the number of nodes in s and t, respectively.
We denote by ∃LBI (existentially linearly-bounded-input) the class of translations satisfying the property
in the theorem. Hence, the theorem statement can be written as follows: Dt MTT∗ ⊆ ∃LBI.
Let us take a look at an example. Consider the following translation ff (a(x1 )) = f (x1 )f (b(x1 , x2 )) = c(f (x1 ))f (e) = dand the tree t = c(d). What is the input tree s that makes f to output t? There are many possibilities,
because f is not injective. Some of them are large (e.g., a(a(a(a(a(a(a(a(a(a(b(a(a(a(a(a(e))))), e)))))))))))),and some are not. In fact, the smallest one b(e, e) is not so large compared to the given tree t. Moreprecisely speaking, the size is ≤ 2|t|. The theorem tells us that this is a universal phenomenon shared among
all MTT-deﬁnable translations.

1.1

The Proof

The problem is broken down to simpler cases by using the following lemma.
Lemma 1.2 ([Man02], Theorem 12). Dt MTT∗ ⊆ Dt LTR ; LBIX ; Y denotes sequential composition: X followed by Y. Dt LTR is the class of total deterministic linear
top-down tree transducers with regular lookahead, whose property is discussed soon. LBI is the class oftranslations that satisﬁes: ∃c ∈ N. ∀s ∈ dom(f ). |s| ≤ c|f (s)|. The class LBI is a strict subclass of ∃LBI.
Let us assume here that Dt LTR ⊆ ∃LBI, then from Lemma 1.2 we can derive the main theorem, because
we can also show the following fact.
Lemma 1.3. ∃LBI ; LBI ⊆ ∃LBI1 .
1 For those who might wonder: it also holds that LBI ; LBI ⊆ LBI. But, ∃LBI ; ∃LBI ̸⊆ ∃LBI and LBI ; ∃LBI ̸⊆ ∃LBI.

1

Proof. Let g1 ∈ ∃LBI, g2 ∈ LBI, and t ∈ range(g1 ; g2 ). Then take arbitrary s0 , s1 satisfying s1 = g1 (s0 ) andt = g2 (s1 ) (since t ∈ range(g1 ; g2 ), there exists at lease one such pair). From the assumption g1 ∈ ∃LBI,
we can make s0 small. That is, by s1 ∈ range(g1 ), there exists s′0 s.t. |s′0 | ≤ cg1 |s1 |. By the LBI-property,|s1 | ≤ cg2 |t|. Hence, we can choose a small input s′0 such that |s′0 | ≤ cg1 cg2 |t|, as desired.
Now, as you expect, the assumption on Dt LTR does hold.
Lemma 1.4. Dt LTR ⊆ ∃LBI.
Proof. By Theorem 2.6 of [Eng77], Dt LTR can be represented as a deterministic ﬁnite-state bottom-up
relabeling followed by Dt LT. Let g be the relabeling and f ∈ Dt LT, and t a tree in the range of g ; f . Let sbe (one of) the minimum input tree such that (g ; f )(s) = t. We will show |s| is bounded by c|t| where c isa constant determined by g and f and independent from t or s.
For each node v of s, we denote by fQ (v) the state of f applied to v during the computation of f (s)(since f is linear transducer, the state, if any, is uniquely determined; if f never visited v, let fq (v) = ⊥).
Note that if fQ (v) = ⊥ then for all nodes v ′ in the subtree rooted at v, we have fQ (v ′ ) = ⊥. We can show|{v | fQ (v) = ⊥}| ≤ r|g|r |{v | fQ (v) ̸= ⊥}| where r is the maximum rank of the label alphabet, and |g| is thenumber of states of the relabeling g. In other words, unvisited parts are smaller than visited parts (ignoring
the constant factor).
The inequation is derived as follows. Let v1 , . . . , vu be the set of nodes that they are unvisited (fQ (vi ) = ⊥)but all their ancestors are visited. It should be clear that u ≤ r|{v | fQ (v) ̸= ⊥}|; there can be at most|{v | fQ (v) ̸= ⊥}| leaves in the visited fragment of s, and each of them can only have at most r unvisitedchildren. Furthermore, the number of nodes of each subtree rooted at vi is bounded by |g|r . Since thesubtree of vi is unvisited, we can freely substitute the subtree to another one without changing the output
t, as long as the bottom-up relabeling g reaches the same state at vi . Here, for any |g|-state tree automatonof rank r, its minimal instance tree is at most |g|r (by the pumping lemma of regular languages, the heightof minimal instance is bounded by |g|). Hence we have the desired inequation.
1
We now know that the 1+r|g|
r fraction of the input tree s is visited by the translation f . Then we have|s|
1+r|g|r≤ |t|, and the proof is done, isn’t it? Unfortunately, no. Even if Dt LT visits an input node, it does
not mean that an output node is generated there. In the only one exceptional case, the transducer may skip
the node without generating any new node. This happens when a rule of the form q(σ(x1 , . . . , xm )) = q ′ (xi )(the form whose rhs is a single state-application) is used at the node. We have to deal with this case.
Let V be the set of skipped nodes of s, i.e., the nodes v such that the right-hand side of the rule of f offor the state-label pair fQ (v), label(v) is a single state-application. Let v1 , v2 , . . . vu ∈ V be a list of nodes
such that vi is the parent node of vi+1 for each i. Then, u must be less than or equal to |f ||g|. This is again
due to the pumping lemma. If the chain is longer than |f ||g|, for some i < j it would be fQ (vi ) = fQ (vj )and gQ (vi ) = gQ (vj ) (where gQ is the unique state used during the run of g on s), which can be shortened
and hence contradicts the minimality of s.
This upper bound of the length implies that at least 1 out of 1 + |f ||g| visited nodes are not skipped andgenerate some output node. In a summary, we have |s| ≤ (1 + r|g|r )(1 + |f ||g|)|t|.

1.2

Nondeterministic Version

I believe the same property holds for nondeterministic MTTs. Analogue of Lemma 1.2 also holds for thenondeterministic case (Theorem 5.10 of [Ina09]). Hence, all I have to do is to show LTR ⊂ ∃LBI. Its proof
should also be similar; after we ﬁx one particular run of the transducer that converts s into t, the same
argument should hold.

2Discussion

Are there any easier proof for the theorem? The theorem may be trivial, just I’m not noticing it...

2

Lemma 1.4 may have something to do with Theorem 5.2 of [AU71], which (if I understand correctly) saysthat the growth rate of a single top-down tree transducer must be in the form √xc or cx for some integer c.
In other words, if the growth rate is less than linear, it is constant (no log n or n translation).
Finally, can we derive something fruitful from the theorem, like linear-time upper bound for some usefulproblem? Currently I have no idea... :pReferences[AU71] Alfred V. Aho and Jeﬀrey D. Ullman. Translations on a context-free grammar. Information andControl, 19:439–475, 1971.
[Bak79] Brenda S. Baker. Composition of top-down and bottom-up tree transductions. Information andControl, 41:186–213, 1979.
[Eng77] Joost Engelfriet. Top-down tree transducers with regular look-ahead. Mathematical Systems Theory,
10:289–303, 1977.
[EV85]

Joost Engelfriet and Heiko Vogler. Macro tree transducers. Journal of Computer and SystemSciences, 31:71–146, 1985.

[Ina09]Kazuhiro Inaba. Complexity and Expressiveness of Models of XML Translations. PhD thesis, The
University of Tokyo, 2009.

[Man02] Sebastian Maneth. The complexity of compositions of deterministic tree transducers. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 265–276, 2002.

3