We study the computational complexity of the parsing problem of a variant of Lambek Categorial Grammar that we call semidirectional. In semidirectional Lambek calculus SD[ there is an additional nondirectional abstraction rule allowing the formula abstracted over to appear anywhere in the premise sequents left-hand side, thus permitting non-peripheral extraction. SD[ grammars are able to generate each context-free language and more than that. We show that the parsing problem for semidireetional Lambek Grammar is NP-complete by a reduction of the 3Partition problem. ...
Nội dung trích xuất từ tài liệu:
Báo cáo khoa học: "Parsing for Semidirectional Lambek Grammar is NP-Complete"
Báo cáo khoa học: Parsing for Semidirectional Lambek Grammar is NP-Complete
Số trang: 6
Loại file: pdf
Dung lượng: 483.91 KB
Lượt xem: 18
Lượt tải: 0
Thông tin tài liệu:
Tìm kiếm theo từ khóa liên quan:
Parsing for Semidirectional Lambek Grammar NP-Complete báo cáo khoa học mô hình ngôn ngữ xử lý ngôn ngữ tự nhiênTài liệu có liên quan:
-
63 trang 355 0 0
-
12 trang 338 0 0
-
Phương pháp tạo ra văn bản tiếng Việt có đề tài xác định
7 trang 285 0 0 -
13 trang 272 0 0
-
Báo cáo khoa học Bước đầu tìm hiểu văn hóa ẩm thực Trà Vinh
61 trang 260 0 0 -
Tóm tắt luận án tiến sỹ Một số vấn đề tối ưu hóa và nâng cao hiệu quả trong xử lý thông tin hình ảnh
28 trang 233 0 0 -
NGHIÊN CỨU CHỌN TẠO CÁC GIỐNG LÚA CHẤT LƯỢNG CAO CHO VÙNG ĐỒNG BẰNG SÔNG CỬU LONG
9 trang 230 0 0 -
Giáo trình Lập trình logic trong prolog: Phần 1
114 trang 224 0 0 -
Đề tài nghiên cứu khoa học và công nghệ cấp trường: Hệ thống giám sát báo trộm cho xe máy
63 trang 218 0 0 -
Đề tài nghiên cứu khoa học: Tội ác và hình phạt của Dostoevsky qua góc nhìn tâm lý học tội phạm
70 trang 198 0 0
