Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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@coli.uni-sb.de mehlhorn@mpi-sb.mpg.de niehren@ps.uni-sb.de 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 e.g. 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 i.e. 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 .
