Pebble Macro Tree Transducers with Strong Pebble Handling

Abstract

We consider pebble macro tree transducers with call-by-name semantics and strong pebble handling. The latter means that the last dropped pebble can be lifted regardless of the position of the reading head. This tree transducer concept is a generalization of the pebblemacro tree transducer introduced by J. Engelfriet and S. Maneth in 2003, however we leave the original name untouched.

Our main results are that (1) every n-pebble macro tree transformation can be characterized by the composition of an n-pebble tree transformation and a yield tree transformation, and (2) each n-pebble tree transformation can also be computed by an (n − 1)-pebble macro tree transformation. Using (1) and (2) we prove that every n-pebblemacro tree transformation appears as the composition of n+2 stay-macro tree transformations and hence, the inverses of n-pebble macro tree transformations preserve regularity. Finally, using the previous results, we show that the type checking problem for n-pebble macro tree transducers is decidable.