TAILIEUCHUNG - Báo cáo khoa học: "Optimal rank reduction for Linear Context-Free Rewriting Systems with Fan-Out Two"

Linear Context-Free Rewriting Systems (LCFRSs) are a grammar formalism capable of modeling discontinuous phrases. Many parsing applications use LCFRSs where the fan-out (a measure of the discontinuity of phrases) does not exceed 2. We present an efficient algorithm for optimal reduction of the length of production right-hand side in LCFRSs with fan-out at most 2. This results in asymptotical running time improvement for known parsing algorithms for this class. | Optimal rank reduction for Linear Context-Free Rewriting Systems with Fan-Out Two Benot Sagot INRIA Universite Paris 7 Le Chesnay France Giorgio Satta Department of Information Engineering University of Padua Italy satta@ Abstract Linear Context-Free Rewriting Systems LCFRSs are a grammar formalism capable of modeling discontinuous phrases. Many parsing applications use LCFRSs where the fan-out a measure of the discontinuity of phrases does not exceed 2. We present an efficient algorithm for optimal reduction of the length of production right-hand side in LCFRSs with fan-out at most 2. This results in asymptotical running time improvement for known parsing algorithms for this class. 1 Introduction Linear Context-Free Rewriting Systems LCFRSs have been introduced by Vijay-Shanker et al. 1987 for modeling the syntax of natural language. The formalism extends the generative capacity of context-free grammars still remaining far below the class of context-sensitive grammars. An important feature of LCFRSs is their ability to generate discontinuous phrases. This has been recently exploited for modeling phrase structure treebanks with discontinuous constituents Maier and Sogaard. 2008 as well as non-projective dependency treebanks Kuhlmann and Satta 2009 . The maximum number f of tuple components that can be generated by an LCFRS G is called the fan-out of G and the maximum number r of nonterminals in the right-hand side of a production is called the rank of G. As an example context-free grammars are LCFRSs with f 1 and r given by the maximum length of a production right-hand side. Tree adjoining grammars Joshi and Levy 1977 can also be viewed as a special kind of LCFRS with f 2 since each auxiliary tree generates two strings and with r given by the maximum number of adjunction and substitution sites in an elementary tree. Beyond tree adjoining languages LCFRSs with f 2 can also generate languages in which pair of strings derived from .

• Báo cáo khoa học
• Optimal rank reduction
• Linear Context Free Rewriting Systems
• Fan Out Two
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Xử lý ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• 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 loại tin tự động
• Tạo chí tin học
• Điều khiển học
• Truy vấn ngôn ngữ tự nhiên
• Phép dịch truy vấn ngôn ngữ tự nhiên
• Truy vấn SQL
• Văn phạm ngữ nghĩa
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Phân tích ngữ nghĩa
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• 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ữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Bài toán PTCP
• Phân tích cú pháp
• 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
• Gán nhãn từ loại
• Ngôn ngữ tự nhiên trong dịch máy
• Hệ thống dịch máy
• Phương pháp xây dựng bảng từ
• Tác từ
• Conditional random fields
• Nhận dạng thực thể có tên
• Đối tượng vật lý trừu tượng
• Phân lớp văn bản
• Biểu diễn nhị phân
• Ma trận từ văn bản
• Wolfram Alpha
• Trích rút thông tin
• Phương pháp Snowball