TAILIEUCHUNG - Báo cáo khoa học: "A Polynomial-Time Fragment of Dominance Constraints"

Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify the natural fragment of normal dominance constraints and show that its satisfiability problem is in deterministic polynomial time. | A Polynomial-Time Fragment of Dominance Constraints Alexander Koller Kurt Mehlhorn Joachim Niehren koller@ mehlhorn@ niehren@ University of the Saarland Max-Planck-Institute for Computer Science Saarbrticken Germany Abstract Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify the natural fragment of normal dominance constraints and show that its satisfiability problem is in deterministic polynomial time. 1 Introduction Dominance constraints are used as partial descriptions of trees in problems throughout computational linguistics. They have been applied to incremental parsing Marcus et al. 1983 grammar formalisms Vijay-Shanker 1992 Rambow et al. 1995 Duchier and Thater 1999 Perrier 2000 discourse Gardent and Webber 1998 and scope underspecification Muskens 1995 Egg et al. 1998 . Logical properties of dominance constraints have been studied . in Backofen et al. 1995 and computational properties have been addressed in Rogers and Vijay-Shanker 1994 Duchier and Gardent 1999 . Here the two most important operations are satisfiability testing - does the constraint describe a tree - and enumerating solutions . the described trees. Unfortunately even the satisfiability problem has been shown to be NP-complete Koller et al. 1998 . This has shed doubt on their practical usefulness. In this paper we define normal dominance constraints a natural fragment of dominance constraints whose restrictions should be unproblematic for many applications. We present a graph algorithm that decides satisfiability of normal dominance constraints in polynomial time. Then we show how to use this algorithm to enumerate solutions efficiently. An example for an application of normal dominance constraints is scope underspecification Constraints as in Fig. 1 can serve as underspecified descriptions of the semantic .

• Báo cáo khoa học
• A Polynomial Time Fragment
• Dominance Constraints
• Alexander Koller Kurt Mehlhorn
• 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