Composition Closure of Linear Extended Top-down Tree Transducers

详细信息    查看全文

• 作者：Joost Engelfriet ; Zoltán Fülöp ; Andreas Maletti
• 关键词：Extended top ; down tree transducer ; Composition hierarchy ; Bimorphism
• 刊名：Theory of Computing Systems
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：60
• 期：2
• 页码：129-171
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1433-0490
• 卷排序：60

文摘

Linear extended top-down tree transducers (or synchronous tree-substitution grammars) are popular formal models of tree transformations that are extensively used in syntax-based statistical machine translation. The expressive power of compositions of such transducers with and without regular look-ahead is investigated. In particular, the restrictions of ε-freeness, strictness, and nondeletion are considered. The composition hierarchy turns out to be finite for all ε-free (all rules consume input) variants of these transducers except for the nondeleting ε-free transducers. The least number of transducers needed for the full expressive power of arbitrary compositions is presented. In all remaining cases (incl. the nondeleting ε-free transducers) the composition hierarchy does not collapse.