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

详细信息    查看全文

• 作者：Bloem ; Roderick ; Engelfriet ; Joost
• 刊名：Journal of Computer and System Sciences
• 出版年：2000
• 出版时间：August, 2000
• 年：2000
• 卷：61
• 期：1
• 页码：1-50
• 全文大小：547 K

文摘

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