A Comparison of Tree Transductions Defined by Monadic Second Order Logic and by Attribute Grammars

摘要: Two well-known formalisms for the specification and computation of tree transductions are compared: mso graph transducer attributed with look-ahead, respectively. The transducer, restricted to trees, uses monadic second order logic define output in terms input tree. is an attribute grammar which all attributes trees; it preceded by a look-ahead phase have finitely many values. main result that these equivalent, i.e., appropriate implementation model specifiable logic. This holds transducers produce trees shared subtrees. If no sharing allowed, satisfies single use restriction.