TAILIEUCHUNG - Báo cáo khoa học: "Parsing for Semidirectional Lambek Grammar is NP-Complete"

We study the computational complexity of the parsing problem of a variant of Lambek Categorial Grammar that we call semidirectional. In semidirectional Lambek calculus SD[ there is an additional nondirectional abstraction rule allowing the formula abstracted over to appear anywhere in the premise sequent's left-hand side, thus permitting non-peripheral extraction. SD[ grammars are able to generate each context-free language and more than that. We show that the parsing problem for semidireetional Lambek Grammar is NP-complete by a reduction of the 3Partition problem. . | Parsing for Semidirectional Lambek Grammar is NP-Complete Jochen Dorre Institut fiir maschinelle Sprachverarbeitung University of Stuttgart Abstract We study the computational complexity of the parsing problem of a variant of Lambek Categorial Grammar that we call semidirectional. In semidirectional Lambek calculus SDL there is an additional non-directional abstraction rule allowing the formula abstracted over to appear anywhere in the premise sequent s left-hand side thus permitting non-peripheral extraction. SDL grammars are able to generate each context-free language and more than that. We show that the parsing problem for semidirectional Lambek Grammar is NP-complete by a reduction of the 3-Partition problem. Key words computational complexity Lambek Categorial Grammar 1 Introduction Categorial Grammar CG and in particular Lambek Categorial Grammar LCG have their well-known benefits for the formal treatment of natural language syntax and semantics. The most outstanding of these benefits is probably the fact that the specific way how the complete grammar is encoded namely in terms of combinatory potentials of its words gives us at the same time recipes for the construction of meanings once the words have been combined with others to form larger linguistic entities. Although both frameworks are equivalent in weak generative capacity both derive exactly the context-free languages LCG is superior to CG in that it can cope in a natural way with extraction and unbounded dependency phenomena. For instance no special category assignments need to be stipulated to handle a relative clause containing a trace because it is analyzed via hypothetical reasoning like a traceless clause with the trace being the hypothesis to be discharged when combined with the relative pronoun. Figure 1 illustrates this proof-logical behaviour. Notice that this natural-deduction-style proof in the type logic corresponds very closely to the phrasestructure tree one would like to adopt in an .

• Báo cáo khoa học
• Parsing for Semidirectional
• Lambek Grammar
• NP Complete
• báo cáo khoa học
• mô hình 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 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