TAILIEUCHUNG - Báo cáo khoa học: "Optimal Head-Driven Parsing Complexity for Linear Context-Free Rewriting Systems"

We study the problem of finding the best headdriven parsing strategy for Linear ContextFree Rewriting System productions. A headdriven strategy must begin with a specified righthand-side nonterminal (the head) and add the remaining nonterminals one at a time in any order. We show that it is NP-hard to find the best head-driven strategy in terms of either the time or space complexity of parsing. | Optimal Head-Driven Parsing Complexity for Linear Context-Free Rewriting Systems Pierluigi Crescenzi Dip. di Sistemi e Informatica Universita di Firenze Daniel Gildea Computer Science Dept. University of Rochester Andrea Marino Dip. di Sistemi e Informatica Universita di Firenze Gianluca Rossi Dip. di Matematica Universita di Roma Tor Vergata Giorgio Satta Dip. di Ingegneria dell Informazione Universita di Padova Abstract We study the problem of finding the best head-driven parsing strategy for Linear Context-Free Rewriting System productions. A head-driven strategy must begin with a specified righthand-side nonterminal the head and add the remaining nonterminals one at a time in any order. We show that it is NP-hard to find the best head-driven strategy in terms of either the time or space complexity of parsing. 1 Introduction Linear Context-Free Rewriting Systems LCFRSs Vijay-Shankar et al. 1987 constitute a very general grammatical formalism which subsumes context-free grammars CFGs and tree adjoining grammars TAGs as well as the synchronous context-free grammars SCFGs and synchronous tree adjoining grammars STAGs used as models in machine LCFRSs retain the fundamental property of CFGs that grammar nonterminals rewrite independently but allow nonterminals to generate discontinuous phrases that is to generate more than one span in the string being produced. This important feature has been recently exploited by Maier and Sogaard 2008 and Kallmeyer and Maier 2010 for modeling phrase structure treebanks with discontinuous constituents and by Kuhlmann and Satta 2009 for modeling non-projective dependency treebanks. The rules of a LCFRS can be analyzed in terms of the properties of rank and fan-out. Rank is the 1To be more precise SCFGs and STAGs generate languages composed by pair of strings while LCFRSs generate string languages. We can abstract away from this difference by assuming concatenation of components in a string pair. 450 number of .

• Báo cáo khoa học
• Optimal Head Driven Parsing Complexity
• Linear Context Free Rewriting Systems
• Pierluigi Crescenzi
• 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