TAILIEUCHUNG - Báo cáo khoa học: "COMPUTATIONAL COMPLEXITY OF CURRENT GPSG THEORY"

An important goal of computational linguistics has been to use linguistic theory to guide the construction of computationally efficient real-world natural language processing systems. At first glance, generalized phrase structure grammar (GPSG) appears to be a blessing on two counts. First, the precise formalisms of GPSG might be a direct and fransparent guide for parser design and implementation. Second, since GPSG has weak context-free generative power and context-free languages can be parsed in O(n ~) by a wide range of algorithms, GPSG parsers would appear to run in polynomial time. This widely-assumed GPSG "efficient parsability" result is misleading: here. | COMPUTATIONAL COMPLEXITY OF CURRENT GPSG THEORY Eric Sven Ristad MIT Artificial Intelligence Lab 545 Technology Square Cambridge MA 02139 Thinking Machines Corporation and 245 First Street Cambridge MA 02142 ABSTRACT An important goal of computational linguistics has been to use linguistic theory to guide the construction of computationally efficient real-world natural language processing systems. At first glance generalized phrase structure grammar GPSG appears to be a blessing on two counts. First the precise formalisms of GPSG might be a direct and transparent guide for parser design and implementation. Second since GPSG has weak context-free generative power and context-free languages can be parsed in o n2 3 by a wide range of algorithms GPSG parsers would appear to run in polynomial time. This widely-assumed GPSG efficient parsability result is misleading here we prove that the universal recognition problem for current GPSG theory is exponential-polynomial time hard and assuredly intractable. The paper pinpoints sources of complexity . metarules and the theory of syntactic features in the current GPSG theory and concludes with some linguistically and computationally motivated restrictions on GPSG. 1 Introduction An important goal of computational linguistics has been to use linguistic theory to guide the construction of computationally efficient real-world natural language processing systems. Generalized Phrase Structure Grammar GPSG linguistic theory holds out considerable promise as an aid in this task. The precise formalisms of GPSG offer the prospect of a direct and transparent guide for parser design and implementation. Furthermore and more importantly GPSG s weak context-free generative power suggests an efficiency advantage for GPSG-based parsers. Since context-free languages can be parsed in polynomial time it seems plausible that GPSGs can also be parsed in polynomial time. This would in turn seem to provide the beginnings of an explanation for the

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.