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

crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.