TAILIEUCHUNG - Báo cáo khoa học: "An Optimal-Time Binarization Algorithm for Linear Context-Free Rewriting Systems with Fan-Out Two"

Linear context-free rewriting systems (LCFRSs) are grammar formalisms with the capability of modeling discontinuous constituents. Many applications use LCFRSs where the fan-out (a measure of the discontinuity of phrases) is not allowed to be greater than 2. We present an efficient algorithm for transforming LCFRS with fan-out at most 2 into a binary form, whenever this is possible. This results in asymptotical run-time improvement for known parsing algorithms for this class. | An Optimal-Time Binarization Algorithm for Linear Context-Free Rewriting Systems with Fan-Out Two Carlos Gomez-Rodriguez Departamento de Computacion Universidade da Coruna Spain cgomezr@ Giorgio Satta Department of Information Engineering University of Padua Italy satta@ Abstract Linear context-free rewriting systems LCFRSs are grammar formalisms with the capability of modeling discontinuous constituents. Many applications use LCFRSs where the fan-out a measure of the discontinuity of phrases is not allowed to be greater than 2. We present an efficient algorithm for transforming LCFRS with fan-out at most 2 into a binary form whenever this is possible. This results in asymptotical run-time improvement for known parsing algorithms for this class. 1 Introduction Since its early years the computational linguistics field has devoted much effort to the development of formal systems for modeling the syntax of natural language. There has been a considerable interest in rewriting systems that enlarge the generative power of context-free grammars still remaining far below the power of the class of contextsensitive grammars see Joshi et al. 1991 for discussion. Following this line Vijay-Shanker et al. 1987 have introduced a formalism called linear context-free rewriting systems LCFRSs that has received much attention in later years by the community. LCFRSs allow the derivation of tuples of strings 1 . discontinuous phrases that turn out to be very useful in modeling languages with relatively free word order. This feature has recently been used for mapping non-projective dependency grammars into discontinuous phrase structures Kuhlmann and Satta 2009 . Furthermore LCFRSs also implement so-called synchronous 1In its more general definition an LCFRS provides a framework where abstract structures can be generated as for instance trees and graphs. Throughout this paper we focus on so-called string-based LCFRSs where rewriting is defined over strings only. .

• Báo cáo khoa học
• An Optimal Time Binarization Algorithm
• Linear Context Free Rewriting Systems
• Fan Out Two
• báo cáo khoa học
• báo cáo ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân tích ngữ nghĩa
• Phân loại tin tự động
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Tách từ tiếng Việt
• Gán nhãn từ loại
• Phân tích cú pháp
• Nghĩa từ vựng
• Phân giải nhập nhằng từ
• Phân loại văn bản
• Lexical chain
• Phản hồi thông tin
• Bài toán PTCP
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học