Abstract
Tree transducers may be used to perform symbolic computations. A function f from (the domain of) one algebra into (the domain of) another algebra is computed by a transduction that yields for every term representing an element a of the input algebra a term representing f(a) in the target algebra. We consider the case where the input algebra is a term algebra, the target algebra is given by the natural numbers with monotonic operations (and in particular maximum, addition, and multiplication), and f is injective. Such an injective function may be seen as a coding of terms as natural numbers. It is shown that codings computed by top-down tree transducers cannot compress totally balanced trees: The binary representation of f(t) has at least the size of t up to a constant factor.
Get full access to this article
View all access options for this article.