Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations Export

@article{citeulike:336896, abstract = {A characterization is given of the class of tree translations definable in monadic second-order logic (MSO), in terms of macro tree transducers. The first main result is that the MSO definable tree translations are exactly those tree translations realized by macro tree transducers (MTTs) with regular look-ahead that are single use restricted. For this the single use restriction known from attribute grammars is generalized to MTTs. Since MTTs are closed under regular look-ahead, this implies that every MSO definable tree translation can be realized by an MTT. The second main result is that the class of MSO definable tree translations can also be obtained by restricting MTTs with regular look-ahead to be finite copying, i.e., to require that each input subtree is processed only a bounded number of times. The single use restriction is a rather strong, static restriction on the rules of an MTT, whereas the finite copying restriction is a more liberal, dynamic restriction on the derivations of an MTT.}, author = {Engelfriet, Joost and Maneth, Sebastian}, citeulike-article-id = {336896}, citeulike-linkout-0 = {http://dx.doi.org/10.1006/inco.1999.2807}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6WGK-45GMFVC-D/2/4e033267dd092454bc3652c9cf185859}, day = {10}, doi = {10.1006/inco.1999.2807}, journal = {Information and Computation}, keywords = {attribute-grammars, mso-logic, tree-transducers}, month = {October}, number = {1}, pages = {34--91}, posted-at = {2005-09-30 13:54:37}, priority = {2}, title = {Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations}, url = {http://dx.doi.org/10.1006/inco.1999.2807}, volume = {154}, year = {1999} }

TY - JOUR ID - citeulike:336896 L3 - citeulike-article-id:336896 N2 - A characterization is given of the class of tree translations definable in monadic second-order logic (MSO), in terms of macro tree transducers. The first main result is that the MSO definable tree translations are exactly those tree translations realized by macro tree transducers (MTTs) with regular look-ahead that are single use restricted. For this the single use restriction known from attribute grammars is generalized to MTTs. Since MTTs are closed under regular look-ahead, this implies that every MSO definable tree translation can be realized by an MTT. The second main result is that the class of MSO definable tree translations can also be obtained by restricting MTTs with regular look-ahead to be finite copying, i.e., to require that each input subtree is processed only a bounded number of times. The single use restriction is a rather strong, static restriction on the rules of an MTT, whereas the finite copying restriction is a more liberal, dynamic restriction on the derivations of an MTT. IS - 1 JF - Information and Computation EP - 91 TI - Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations VL - 154 SP - 34 KW - attribute-grammars KW - mso-logic KW - tree-transducers AU - Engelfriet, Joost AU - Maneth, Sebastian PY - 1999/10/10/ UR - http://dx.doi.org/10.1006/inco.1999.2807 ER -