A characterization of attributed tree transformations by a subclass of macro tree transducers

Authors
Fulop, Z Vogler, H
Citation
Z. Fulop et H. Vogler, A characterization of attributed tree transformations by a subclass of macro tree transducers, THEOR C SYS, 32(6), 1999, pp. 649-676
Citations number
29
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORY OF COMPUTING SYSTEMS
ISSN journal
14324350 → ACNP
Volume
32
Issue
6
Year of publication
1999
Pages
649 - 676
Database
ISI
SICI code
1432-4350(199911/12)32:6<649:ACOATT>2.0.ZU;2-9
Abstract
We present a characterization of the class of tree transformations computed by (noncircular) attributed tree transducers, in terms of a subclass of ma cro tree transducers, called attributed-like macro tree transducers. In fac t, we prove formally that attributed tree transducers and attributed-like m acro tree transducers generate the same class of tree transformations. More over, we prove that it is decidable whether a macro tree transducer is attr ibuted-like.