Circularity, Composition, and Decomposition Results for Pebble Macro Tree Transducers

The pebble tree transducer is a model for XML query languages while the macro tree transducer is a well-known model for syntax-directed semantics. We consider their combination, called pebble macro tree transducer (using outside-in semantics). We define weakly circular, circular and strongly circular pebble macro tree transducers and show that each of these circularity problems for pebble tree macro transducers are decidable. We consider composition and decomposition of pebble macro tree transformations. We show that (1) every not weakly circular deterministic n-pebble macro tree transformation can be decomposed into a noncircular deterministic n-pebble tree transformation and a partial deterministic yield tree transformation and (2) every not weakly circular context-linear n-pebble macro tree transformation can be decomposed into a noncircular n-pebble tree transformation and a partial deterministic yield tree transformation. We use these results to give a partial solution to an open problem. Namely, we show that (1) the class of not weakly circular deterministic 0-pebble macro tree transformations is a subset of the two-fold composition of the class of noncircular deterministic 0-pebble tree transformations and (2) the class of not weakly circular context-linear 0-pebble macro tree transformations is a subset of the two-fold composition of the class of noncircular 0-pebble tree transformations. Finally, we show that the compositions of pebble tree transformations and yield tree transformations are pebble macro tree transformations.