TAILIEUCHUNG - Báo cáo khoa học: "AN EFFICIENT PARSING ALGORITHM FOR TREE ADJOINING GRAMMARS"

In the literature, Tree Adjoining Grammars (TAGs) are propagated to be adequate for natural language description - - analysis as well as generation. In this paper we concentrate on the direction of analysis. Especially important for an implementation of that task is how efficiently this can be done, ., how readily the word problem can be solved for TAGs. Up to now, a parser with O(n 6) steps in the worst case was known where n is the length of the input string. In this paper, the result is improved to O(n 4 log n) as a new lowest. | AN EFFICIENT PARSING ALGORITHM FOR TREE ADJOINING GRAMMARS Karin Harbusch DFKI - Deutsches Forschungszentrum fur Kũnstỉiche Intelligenz Stuhlsatzenhausweg 3 D-6600 Saarbrucken 11 . harbusch@ de ABSTRACT In the literature Tree Adjoining Grammars TAGs are propagated to be adequate for natural language description analysis as well as generation. In this paper we concentrate on the direction of analysis. Especially important for an implementation of that task is how efficiently this can be done . how readily the word problem can be solved for TAGs. Up to now a parser with 0 ne steps in the worst case was known where n is the length of the input string. In this paper the result is improved to 0 n4 log n as a new lowest upper bound. The paper demonstrates how local interpretion of TAG trees allows this reduction. 1 INTRODUCTION Compared with the formalism of contexi-free grammars CFGs the rules of Tree Adjoining Grammars TAGs can be imagined intuitively as parts of context-free derivation trees. Without paying attention to the fact that there are some more restrictions for these rules the recursion operation adjoining is represented as replacing a node in a TAG rule by another TAG rule so that larger derivation trees are built. This close relation between CFGs and TAGs can imply that they are equivalent. But TAGs are more powerful than context-free grammars. This additional power characterized as mildly context-sensitive leads to the question of whether there are efficient algorithms to solve the word problem for TAGs. Up to now the algorithm of Vijay-Shanker and Joshi with a time complexity of 0 n6 for the worst case was known in addition to several unsuccessful attempts to improve this result. This paper s main emphasis is on the improvement of this result. An efficient parser for Tree Adjoining Grammars with a worst case time complexity of 0 n4 log n is discussed. All known parsing algorithms for TAGs use the close structural similarity between TAGs

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.