A Characterization of Attributed Tree Transformations by a Subclass of Macro Tree Transducers

We present a characterization of the class of tree transformations computed by (noncircular) attributed tree transducers, in terms of a subclass of macro tree transducers, called attributed-like macro tree transducers. In fact, we prove formally that attributed tree transducers and attributed-like macro tree transducers generate the same class of tree transformations. Moreover, we prove that it is decidable whether a macro tree transducer is attributed-like.

Authors and Affiliations

1. Department of Computer Science, Jósef Attila University, Árpád tér 2., H-6720 Szeged, Hungary fulop@inf.u-szeged.hu, , , , , , HU

   Z. Fülöp

2. Department of Computer Science, Technical University of Dresden, D-01062 Dresden, Germany vogler@inf.tu-dresden.de, , , , , , DE

   H. Vogler

Received December 1997, and revised form October 1998, and in final form January 1999.

Reprints and permissions