Linear deterministic multi bottom-up tree transducers

In general, top-down and bottom-up tree transducers lead to incomparable classes of tree transformations, both for the nondeterministic and the deterministic case. If deterministic top-down tree transducers are extended by the capability to recognize regular tree properties and deterministic bottom-up tree transducers are generalized by allowing states with arbitrary finite rank, then the two devices, now called deterministic top-down tree transducers with regular look-ahead and deterministic multi bottom-up tree transducers, respectively, become equivalent [Z. Fulop, A. Kuhnemann, H. Vogler, A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead, Inform. Process. Lett. 91 (2004) 57-67]. In this paper we focus on the class ld-MBOT of tree transformations which are computed by linear deterministic multi bottom-up tree transducers. We investigate the relationship among Id-MBOT and the classes of tree transformations computed by (restricted) deterministic bottom-up tree transducers and by (restricted) deterministic top-down tree transducers with regular look-ahead. In fact, we show the inclusion diagram of nine such classes. (c) 2005 Elsevier B.V. All rights reserved.