Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
A characterization of the expressive power of synchronous tree-adjoining grammars (STAGs) in terms of tree transducers (or equivalently, synchronous tree substitution grammars) is developed. Essentially, a STAG corresponds to an extended tree transducer that uses explicit substitution in both the input and output. This characterization allows the easy integration of STAG into toolkits for extended tree transducers. Moreover, the applicability of the characterization to several representational and algorithmic problems is demonstrated. . | A Tree Transducer Model for Synchronous Tree-Adjoining Grammars Andreas Maletti Universitat Rovira i Virgili Avinguda de Catalunya 25 43002 Tarragona Spain. andreas.maletti@urv.cat Abstract A characterization of the expressive power of synchronous tree-adjoining grammars STAGs in terms of tree transducers or equivalently synchronous tree substitution grammars is developed. Essentially a STAG corresponds to an extended tree transducer that uses explicit substitution in both the input and output. This characterization allows the easy integration of STAG into toolkits for extended tree transducers. Moreover the applicability of the characterization to several representational and algorithmic problems is demonstrated. 1 Introduction Machine translation has seen a multitude of formal translation models. Here we focus on syntaxbased or tree-based models. One of the oldest models is the synchronous context-free grammar Aho and Ullman 1972 . It is clearly too weak as a syntax-based model but found use in the string-based setting. Top-down tree transducers Rounds 1970 Thatcher 1970 have been heavily investigated in the formal language community Gecseg and Steinby 1984 Gecseg and Steinby 1997 but as argued by Shieber 2004 they are still too weak for syntax-based machine translation. Instead Shieber 2004 proposes synchronous tree substitution grammars STSGs and develops an equivalent bimorphism Arnold and Dauchet 1982 characterization. This characterization eventually led to the rediscovery of extended tree transducers Graehl and Knight 2004 Knight and Graehl 2005 Graehl et al. 2008 which are essentially as powerful as STSG. They had been studied already by Arnold and Dauchet 1982 in the form of bimorphisms but received little attention until rediscovered. Shieber 2007 claims that even STSGs might be too simple to capture naturally occuring transla tion phenomena. Instead Shieber 2007 suggests a yet more powerful mechanism synchronous tree-adjoining grammars STAGs as .
