Bridging the Gap Between Underspecification Formalisms: Minimal Recursion Semantics as Dominance Constraints

Bridging the Gap Between Underspecification Formalisms: Minimal Recursion Semantics as Dominance Constraints Joachim Niehren Programming Systems Lab Universit¨at des Saarlandes niehren@ps.uni-sb.de Stefan Thater Computational Linguistics Universit¨at des Saarlandes stth@coli.uni-sb.de Abstract Minimal Recursion Semantics (MRS) is the standard formalism used in large-scale HPSG grammars to model underspecified semantics. We present the first provably efficient algorithm to enumerate the read- ings of MRS structures, by translating them into normal dominance constraints. 1 Introduction In the past few years there has been considerable activity in the development of formalisms for un- derspecified semantics (Alshawi and Crouch, 1992; Reyle, 1993; Bos, 1996; Copestake et al., 1999; Egg et al., 2001). The common idea is to delay the enu- meration of all readings for as long as possible. In- stead, they work with a compact underspecified rep- resentation; readings are enumerated from this rep- resentation by need. Minimal Recursion Semantics (MRS) (Copes- take et al., 1999) is the standard formalism for se- mantic underspecification used in large-scale HPSG grammars (Pollard and Sag, 1994; Copestake and Flickinger, ). Despite this clear relevance, the most obvious questions about MRS are still open: 1. Is it possible to enumerate the readings of MRS structures efficiently? No algorithm has been published so far. Existing implementa- tions seem to be practical, even though the problem whether an MRS has a reading is NP- complete (Althaus et al., 2003, Theorem 10.1). 2. What is the precise relationship to other un- derspecification formalism? Are all of them the same, or else, what are the differences? We distinguish the sublanguages of MRS nets and normal dominance nets, and show that they can be intertranslated. This translation answers the first question: existing constraint solvers for normal dominance constraints can be used to enumerate the readings of MRS nets in low polynomial time. The translation also answers the second ques- tion restricted to pure scope underspecification. It shows the equivalence of a large fragment of MRSs and a corresponding fragment of normal dominance constraints, which in turn is equivalent to a large fragment of Hole Semantics (Bos, 1996) as proven in (Koller et al., 2003). Additional underspecified treatments of ellipsis or reinterpretation, however, are available for extensions of dominance constraint only (CLLS, the constraint language for lambda structures (Egg et al., 2001)). Our results are subject to a new proof tech- nique which reduces reasoning about MRS struc- tures to reasoning about weakly normal dominance constraints (Bodirsky et al., 2003). The previous proof techniques for normal dominance constraints (Koller et al., 2003) do not apply. 2 Minimal Recursion Semantics We define a simplified version of Minimal Recur- sion Semantics and discuss differences to the origi- nal definitions presented in (Copestake et al., 1999). MRS is a description language for formulas of first order object languages with generalized quanti- fiers. Underspecified representations in MRS consist of elementary predications and handle constraints. Roughly, elementary predications are object lan- guage formulas with “holes” into which other for- mulas can be plugged; handle constraints restrict the way these formulas …

Content truncated to 500 words