TAILIEUCHUNG - Báo cáo khoa học: "Constraints on strong generative power"

We consider the question “How much strong generative power can be squeezed out of a formal system without increasing its weak generative power?” and propose some theoretical and practical constraints on this problem. We then introduce a formalism which, under these constraints, maximally squeezes strong generative power out of context-free grammar. Finally, we generalize this result to formalisms beyond CFG. | Constraints on strong generative power David Chiang University of Pennsylvania Dept of Computer and Information Science 200 S 33rd St Philadelphia PA 19104 USA dchiang@ Abstract We consider the question How much strong generative power can be squeezed out of a formal system without increasing its weak generative power and propose some theoretical and practical constraints on this problem. We then introduce a formalism which under these constraints maximally squeezes strong generative power out of context-free grammar. Finally we generalize this result to formalisms beyond CFG. 1 Introduction How much strong generative power can be squeezed out of a formal system without increasing its weak generative power This question posed by Joshi 2000 is important for both linguistic description and natural language processing. The extension of tree adjoining grammar TAG to tree-local multicomponent TAG Joshi 1987 or the extension of context free grammar CFG to tree insertion grammar Schabes and Waters 1993 or regular form TAG Rogers 1994 can be seen as steps toward answering this question. But this question is difficult to answer with much finality unless we pin its terms down more precisely. First what is meant by strong generative power In the standard definition Chomsky 1965 a grammar G weakly generates a set of sentences L G and strongly generates a set of structural descriptions X G the strong generative capacity of a formalism F is then Z G I F provides G . There is some vagueness in the literature however over what structural descriptions are and how they can reasonably be compared across theories Miller 1999 gives a good synopsis . a X A 6 X a X X b b XNA a X b b X a Figure 1 Example of weakly context-free TAG. The approach that Vijay-Shanker et al. 1987 and Weir 1988 take elaborated on by Becker et al. 1992 is to identify a very general class of formalisms which they call linear context-free rewriting systems CFRSs and define for this class a large space

• Báo cáo khoa học
• Constraints on strong
• generative power
• David Chiang
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Mathematical programming with equilibrium constraint
• Sufficient optimality condition
• Higher order strong convexity
• Strict local minima
• Optimization problem
• 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