tailieunhanh - Báo cáo khoa học: "Another Facet of LIG Parsing"

In this paper 1 we present a new parsing algorithm for linear indexed grammars (LIGs) in the same spirit as the one described in (Vijay-Shanker and Weir, 1993) for tree adjoining grammars. For a LIG L and an input string x of length n, we build a non ambiguous context-free grammar whose sentences are all (and exclusively) valid derivation sequences in L which lead to x. We show that this grammar can be built in (9(n 6) time and that individual parses can be extracted in linear time with the size of the extracted parse tree. Though this O(n. | Another Facet of LIG Parsing Pierre Boullier INRIA-Rocquencourt BP 105 78153 Le Chesnay Cedex France Abstract In this paper1 we present a new parsing algorithm for linear indexed grammars LIGs in the same spirit as the one described in Vijay-Shanker and Weir 1993 for tree adjoining grammars. For a LIG L and an input string X of length n we build a non ambiguous context-free grammar whose sentences are all and exclusively valid derivation sequences in L which lead to X. We show that this grammar can be built in O n6 time and that individual parses can be extracted in linear time with the size of the extracted parse tree. Though this ỡ n6 upper bound does not improve over previous results the average case behaves much better. Moreover practical parsing times can be decreased by some statically performed computations. 1 Introduction The class of mildly context-sensitive languages can be described by several equivalent grammar types. Among these types we can notably cite tree adjoining grammars TAGs and linear indexed grammars LIGs . In Vijay-Shanker and Weir 1994 TAGs are transformed into equivalent LIGs. Though context-sensitive linguistic phenomena seem to be more naturally expressed in TAG formalism from a computational point of view many authors think that LIGs play a central role and therefore the understanding of LIGs and LIG parsing is of importance. For example quoted from Schabes and Shieber 1994 The LIG version of TAG can be used for recognition and parsing. Because the LIG formalism is based on augmented rewriting the parsing algorithms can be much simpler to understand rSee Boullier 1996 for an extended version. and easier to modify and no loss of generality is incurred . In Vijay-Shanker and Weir 1993 LIGs are used to express the derivations of a sentence in TAGs. In Vijay-Shanker Weir and Rambow 1995 the approach used for parsing a new formalism the D-Tree Grammars DTG is to translate a DTG into a Linear Prioritized Multiset .

• Báo cáo khoa học
• Another Facet
• LIG Parsing
• Pierre Boullier
• 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