Well-Nested Parallelism Constraints for Ellipsis Resolution

Well-Nested Parallelism Constraints for Ellipsis Resolution Katrin Erk and Joachim Niehren Saarland University, Saarbriicken, Germany erk@coli.uni - sb.de / niehren@ps.uni - sb.de Abstract The Constraint Language for Lambda Structures (CLLS) is an expressive tree description language. It provides a uni- form framework for underspecified se- mantics, covering scope, ellipsis, and anaphora. Efficient algorithms exist for the sublanguage that models scope. But so far no terminating algorithm exists for sublanguages that model ellipsis. We introduce well-nested parallelism con- straints and show that they solve this problem. 1 Introduction Ellipsis phenomena are ubiquitous in natural lan- guage, e.g. in VP ellipsis, answers to questions, and corrections. They have been studied exten- sively (Sag, 1976; Williams, 1977; Fiengo and May, 1994; Dalrymple et al., 1991; Hardt, 1993; Kehler, 1995; Lappin and Shih, 1996) but remain difficult to handle. Among the problems to solve in connection with ellipsis are: determining the el- lipsis antecedent, constructing a description of the ellipsis meaning, and resolving the ellipsis (i.e. ac- tually determining its meaning). In this paper we focus on the problem of resolving ellipsis. We as- sume an analysis of its structure (source, target, and parallel elements) in the Constraint Language for Lambda Structures (CLLS) (Egg et al., 2001). CLLS is an expressive tree description language that provides a uniform framework for seman- tic underspecification covering scope, ellipsis, and anaphora. CLLS offers dominance constraints for modeling scope ambiguity in a similar way as pre- vious approaches (Reyle, 1993; Pinkal, 1995; Bos, 1996), parallelism constraints for modeling ellip- sis, and anaphoric links for modeling coreference. The interaction of ellipsis with scope (quantifier parallelism) is handled in a modular fashion. Enu- merating scope readings becomes solving domi- nance constraints, while ellipsis resolution is re- duced to solving parallelism constraints. Constraint solving subsumes satisfiability checking. Satisfiability of dominance constraints is NP-complete (Koller et al., 2001). But for modeling scope underspecification a sublanguage of constraints suffices. These constraints can be solved in low polynomial time (Althaus et al., 2002). Parallelism constraints are as expressive as the language of Context Unification, the satisfiability problem of which is prominent but still open (Comon, 1992). A lower bound is given by string unification (Makanin, 1977), for which the best known algorithm runs in PSPACE. So far, no terminating algorithm exists for sub- languages of CLLS that model ellipsis. The sound and complete semi-decision procedure for CLLS (Erk et al., 2002) can be used for this purpose but is slow in practice and not guaranteed to terminate. In the current paper we introduce well-nested parallelism constraints and so solve this prob- lem for the first time. We argue that well-nested parallelism constraints are powerful enough to model ellipsis, in particular VP-ellipsis. We present a solver for well-nested parallelism con- straints which decides satisfiability in nondeter- ministic polynomial time, and hence proves the NP-completeness of this problem, as dominance constraints are subsumed. 2 CLLS We represent the meaning of sentences by lambda terms, which are seen as trees and then described 115 by formulas of …

Content truncated to 500 words