A LOWER BOUND ON THE GROWTH OF FUNCTIONS COMPUTED BY TREE TRANSDUCERS

Article type: Research Article

Authors: Drewes, Frank

Affiliations: Universität Bremen, Fachbereich 3, D-28334 Bremen, Germany. E-mail: [email protected]

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.

DOI: 10.3233/FI-1996-263403

Journal: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 267-285, 1996