tailieunhanh - Báo cáo khoa học: "Optimal k-arization of Synchronous Tree-Adjoining Grammar"

Synchronous Tree-Adjoining Grammar (STAG) is a promising formalism for syntaxaware machine translation and simultaneous computation of natural-language syntax and semantics. Current research in both of these areas is actively pursuing its incorporation. However, STAG parsing is known to be NP-hard due to the potential for intertwined correspondences between the linked nonterminal symbols in the elementary structures. Given a particular grammar, the polynomial degree of efficient STAG parsing algorithms depends directly on the rank of the grammar: the maximum number of correspondences that appear within a single elementary structure. . | Optimal k-arization of Synchronous Tree-Adjoining Grammar Rebecca Nesson School of Engineering and Applied Sciences Harvard University Cambridge MA 02138 nesson@ Giorgio Satta Department of Information Engineering University of Padua I-35131 Padova Italy satta@ Stuart M. Shieber School of Engineering and Applied Sciences Harvard University Cambridge MA 02138 shieber@ Abstract Synchronous Tree-Adjoining Grammar STAG is a promising formalism for syntax-aware machine translation and simultaneous computation of natural-language syntax and semantics. Current research in both of these areas is actively pursuing its incorporation. However STAG parsing is known to be NP-hard due to the potential for intertwined correspondences between the linked nonterminal symbols in the elementary structures. Given a particular grammar the polynomial degree of efficient STAG parsing algorithms depends directly on the rank of the grammar the maximum number of correspondences that appear within a single elementary structure. In this paper we present a compile-time algorithm for transforming a STAG into a strongly-equivalent STAG that optimally minimizes the rank k across the grammar. The algorithm performs in O G Y Lg time where LG is the maximum number of links in any single synchronous tree pair in the grammar and Y is the set of synchronous tree pairs of G. 1 Introduction Tree-adjoining grammar is a widely used formalism in natural-language processing due to its mildly-context-sensitive expressivity its ability to naturally capture natural-language argument substitution via its substitution operation and optional modification via its adjunction operation and the existence of efficient algorithms for processing it. Recently the desire to incorporate syntax-awareness into machine translation systems has generated interest in the application of synchronous tree-adjoining grammar STAG to this problem Nesson Shieber and Rush 2006 Chiang and Rambow