Expanding the Range of Tractable Scope-Underspecified Semantic Representations

First Joint Conference on Lexical and Computational Semantics (*SEM), pages 142–150, Montr´eal, Canada, June 7-8, 2012. c⃝2012 Association for Computational Linguistics Expanding the Range of Tractable Scope-Underspecified Semantic Representations Mehdi Manshadi and James Allen Department of Computer Science University of Rochester Rochester, NY 14627 {mehdih,james}@cs.rochester.edu Abstract Over the past decade, several underspec- ification frameworks have been proposed that efficiently solve a big subset of scope- underspecified semantic representations within the realm of the most popular constraint-based formalisms. However, there exists a family of coherent natural language sentences whose underspecified representa- tion does not belong to this subset. It has remained an open question whether there ex- ists a tractable superset of these frameworks, covering this family. In this paper, we show that the answer to this question is yes. We define a superset of the previous frameworks, which is solvable by similar algorithms with the same time and space complexity. 1 Introduction Scope ambiguity is a major source of ambiguity in semantic representation. For example, the sentence 1. Every politician has a website. has at least two possible interpretations, one in which each politician may have a different website (i.e., Every has wide scope) and one in which there is a unique website for all the politicians (i.e., Every has narrow scope). Since finding the most preferred reading automatically is very hard, the most widely adopted solution is to use an Underspecified Rep- resentation (UR), that is to encode the ambiguity in the semantic representation and leave scoping un- derspecified. In an early effort, Woods (1986) developed an un- scoped logical form where the above sentence is rep- resented (roughly) as the formula: 2. Has(⟨Every x Politician⟩, ⟨A y Website⟩) To obtain a fully scoped formula, the quantifiers are pulled out one by one and wrapped around the formula. If we pull out Every first, we produce the fully-scoped formula: 3. A(y, Website(y), Every(x, Politician(x), Has(x, y)) If we had pulled out A first, we would have had the other reading, with Every having wide scope. Hobbs and Shieber (1987) extend this formalism to support operators (such as not) and present an enumeration algorithm that is more efficient than the naive wrapping approach. Since the introduction of Quasi Logical Form (Al- shawi and Crouch, 1992), there has been a lot of work on designing constraint-based underspecifica- tion formalisms where the readings of a UR are not defined in a constructive fashion as shown above, but rather by a set of constraints. A fully-scoped struc- ture is a reading iff it satisfies all the constraints. The advantage of these frameworks is that as the pro- cessing goes deeper, new (say pragmatically-driven) constraints can be added to the representation in or- der to filter out unwanted readings. Hole Seman- tics (Bos, 1996; Bos, 2002), Constraint Language for Lambda Structures (CLLS) (Egg et al., 2001), and Minimal Recursion Semantics (MRS) (Copes- take et al., 2001) are among these frameworks. In an effort to bridge the gap between the above formalisms, a graph theoretic …

Content truncated to 500 words