A Polynomial-Time Fragment of Dominance Constraints

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 Saarbr¨ucken, 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 through- out computational linguistics. They have been applied to incremental parsing (Mar- cus 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 un- derspecification (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 satisfia- bility testing – does the constraint describe a tree? – and enumerating solutions, i.e. the described trees. Unfortunately, even the sat- isfiability 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 domi- nance constraints, a natural fragment of dom- inance constraints whose restrictions should be unproblematic for many applications. We present a graph algorithm that decides sat- isfiability of normal dominance constraints in polynomial time. Then we show how to use this algorithm to enumerate solutions ef- ficiently. An example for an application of normal dominance constraints is scope underspecifi- cation: Constraints as in Fig. 1 can serve as underspecified descriptions of the semantic readings of sentences such as (1), considered as the structural trees of the first-order rep- resentations. The dotted lines signify domi- nance relations, which require the upper node to be an ancestor of the lower one in any tree that fits the description. (1) Some representative of every department in all companies saw a sample of each product. The sentence has 42 readings (Hobbs and Shieber, 1987), and it is easy to imagine how the number of readings grows exponen- tially (or worse) in the length of the sen- tence. Efficient enumeration of readings from the description is a longstanding problem in scope underspecification. Our polynomial algorithm solves this problem. Moreover, the investigation of graph problems that are closely related to normal constraints allows us to prove that many other underspecification formalisms – e.g. Minimal Recursion Seman- tics (Copestake et al., 1997) and Hole Seman- tics (Bos, 1996) – have NP-hard satisfiability problems. Our algorithm can still be used as a preprocessing step for these approaches; in fact, experience shows that it seems to solve all encodings of descriptions in Hole Seman- tics that actually occur. ∀u • → • comp • u • • ∀w • → • ∧ • • dept • w • • ∃x • ∧ • ∧ …

Content truncated to 500 words