Pebble Macro Tree Transducers with Strong Pebble Handling

Article type: Research Article

Authors: Fülöp, Zoltán | Muzamel, Loránd

Affiliations: Department of Foundations of Computer Science, University of Szeged, Árpád tér 2., H-6720 Szeged, Hungary. fulop@inf.u-szeged.hu; muzamel@inf.u-szeged.hu

Note: [] Address for correspondence: Department of Foundations of Computer Science, University of Szeged, Árpád tér 2., H-6720 Szeged, Hungary

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.

Journal: Fundamenta Informaticae, vol. 89, no. 2-3, pp. 207-257, 2008