TAILIEUCHUNG - Báo cáo khoa học: "Capturing CFLs with Tree Adjoining Grammars"

We define a decidable class of TAGs that is strongly equivalent to CFGs and is cubic-time parsable. This class serves to lexicalize CFGs in the same manner as the LC, FGs of Schabes and Waters but with considerably less restriction on the form of the grammars. The class provides a nornlal form for TAGs that generate local sets m rnuch the same way that regular g r a m m a r s provide a normal form for CFGs that generate regular sets. Introduction We introduce the notion of Regular Form for Tree Adjoining ( ; r a m. | Capturing CFLs with Tree Adjoining Grammars James Rogers Dept of Computer and Information Sciences University of Delaware Newark DE 19716 USA j Abstract We define a decidable class of TAGs that is strongly equivalent to CFGs and is cubic-time parsable. This class serves to lexicalize CFGs in the same manner as the LCFGs of Schabes and Waters but with considerably less restriction on the form of the grammars. The class provides a normal form for TAGs that generate local sets in much the same way that regular grammars provide a normal form for CFGs that generate regular sets. Introduction We introduce the notion of Regular Form for Tree Adjoining Grammars TAGs . The class of TAGs that are in regular from is equivalent in strong generative capacity 1 to the Context-Free Grammars that is the sets of trees generated by TAGs in this class are the local sets the sets of derivation trees generated by Our investigations were initially motivated by the work of Schabes Joshi and Waters in lexicalization of CFGs via TAGs Schabes and Joshi 1991 Joshi and Schabes 1992 Schabes and Waters 1993a Schabes and Waters 1993b Schabes 1990 . The class we describe not only serves to lexicalize CFGs in a way that is more faithful and more flexible in its encoding than earlier work but provides a basis for using the more expressive TAG formalism to define Context-Free Languages CFLs. In Schabes et al. 1988 and Schabes 1990 a general notion of grammars is introduced. A grammar is lexicalized in this sense if each of the basic structures it manipulates is associated with a lexical item its anchor. The set of structures relevant to a particular input string then is selected by the lexical The work reported here owes a great deal to extensive discussions with K. Vijay-Shanker. 1 We will refer to equivalence of the sets of trees generated by two grammars or classes of grammars as strong equivalence. Equivalence of their string languages will be referred to

• Báo cáo khoa học
• Capturing CFLs
• Tree Adjoining Grammars
• Long Papers
• 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