tailieunhanh - Báo cáo khoa học: "Efficient Parsing for Bilexical Context-Free Grammar sand Head Automaton Grammars*"

Several recent stochastic parsers use bilexical grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present O(n 4) parsing algorithms for two bilexical formalisms, improving the prior upper bounds of O(n5). For a common special case that was known to allow O(n 3) parsing (Eisner, 1997), we present an O(n 3) algorithm with an improved grammar constant. | Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars Jason Eisner Giorgio Satta Dept of Computer Information Science Dip. di Elettronica e Informatica University of Pennsylvania Università di Padova 200 South 33rd Street via Gradenigo 6 A Philadelphia PA 19104 USA 35131 Padova Italy jeisner@ satta@ Abstract Several recent stochastic parsers use bilexical grammars where each word type idiosyncrat-ically prefers particular complements with particular head words. We present O n4 parsing algorithms for two bilexical formalisms improving the prior upper bounds of O n5 . For a common special case that was known to allow O n3 parsing Eisner 1997 we present an ơ n3 algorithm with an improved grammar constant. 1 Introduction Lexicalized grammar formalisms are of both theoretical and practical interest to the computational linguistics community. Such formalisms specify syntactic facts about each word of the language in particular the type of arguments that the word can or must take. Early mechanisms of this sort included categorial grammar Bar-Hillel 1953 and subcategorization frames Chomsky 1965 . Other lexi-calized formalisms include Schabes et al. 1988 Mel cuk 1988 Pollard and Sag 1994 . Besides the possible arguments of a word a natural-language grammar does well to specify possible head words for those arguments. Convene requires an NP object but some NPs are more semantically or lexically appropriate here than others and the appropriateness depends largely on the NP s head . meeting . We use the general term bilexical for a grammar that records such facts. A bilexical grammar makes many stipulations about the compatibility of particular pairs of words in particular roles. The acceptability of Nora convened the The authors were supported respectively under ARPA Grant N6600194-C-6043 Human Language Technology and Ministero dell Universita e della Ricerca Scientifica e Tecnologica project Methodologies and .

• Báo cáo khoa học
• Efficient Parsing
• Bilexical Context Free Grammar
• Head Automaton Grammars
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• A Bag of Useful
• Techniques for Efficient
• Robust Parsing
• Efficient Normal Form Parsing
• Combinatory Categorial Grammar
• Jason Eisner
• EFFICIENT PARSING FOR FRENCH
• Claire Gardent
• Long Papers
• scientific reports
• model language
• process natural language
• AN EFFICIENT PARSING ALGORITHM
• TREE ADJOINING GRAMMARS
• Karin Harbusch
• Towards efficient parsing
• proof nets
• 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