A comparison of pebble tree transducers with macro tree transducers

The n-pebble tree transducer was recently proposed as a model for XML query languages. The four main results on deterministic transducers are: First, (1) the translation \(\tau\) of an n-pebble tree transducer can be realized by a composition of n+1 0-pebble tree transducers. Next, the pebble tree transducer is compared with the macro tree transducer, a well-known model for syntax-directed semantics, with decidable type checking. The -pebble tree transducer can be simulated by the macro tree transducer, which, by the first result, implies that (2) \(\tau\) can be realized by an (n+1)-fold composition of macro tree transducers. Conversely, every macro tree transducer can be simulated by a composition of 0-pebble tree transducers. Together these simulations prove that (3) the composition closure of n-pebble tree transducers equals that of macro tree transducers (and that of 0-pebble tree transducers). Similar results hold in the nondeterministic case. Finally, (4) the output languages of deterministic n-pebble tree transducers form a hierarchy with respect to the number n of pebbles.

Authors and Affiliations

1. LIACS, Leiden University, PO Box 9512, 2300 RA, Leiden, The Netherlands

   Joost Engelfriet & Sebastian Maneth

Corresponding author

Correspondence to Joost Engelfriet.

Received: 16 January 2003,

Sebastian Maneth: Present address: Swiss Institute of Technology Lausanne, Programming Methods Laboratory (LAMP), 1015 Lausanne, Switzerland, e-mail (sebastian.maneth@epfl.ch)

Reprints and permissions