A Theory of Scope Underspecification

Abstract

The general problem of finding satisfying solutions to
constraint-based underspecified representations of quantifier
scope is NP-complete.  Existing frameworks, including Dominance
Graphs, Minimal Recursion Semantics, and Hole Semantics, have
struggled to balance expressivity and tractability, in order to
cover real natural language sentences with efficient algorithms.
We address this trade-off with a general principle of coherence,
which requires that every variable introduced in the domain of discourse must
contribute to the overall semantics of the sentence.  We show
that every underspecified representation meeting this criterion
can be efficiently processed, and that our set of representations
subsumes all previously identified tractable sets.