Underspecified Beta Reduction

Underspecified Beta Reduction Manuel Bodirsky Katrin Erk Joachim Niehren Programming Systems Lab Saarland University D-66041 Saarbr¨ucken, Germany {bodirsky|erk|niehren}@ps.uni-sb.de Alexander Koller Department of Computational Linguistics Saarland University D-66041 Saarbr¨ucken, Germany koller@coli.uni-sb.de Abstract For ambiguous sentences, traditional semantics construction produces large numbers of higher-order formulas, which must then be � -reduced individ- ually. Underspecified versions can pro- duce compact descriptions of all read- ings, but it is not known how to perform � -reduction on these descriptions. We show how to do this using � -reduction constraints in the constraint language for � -structures (CLLS). 1 Introduction Traditional approaches to semantics construction (Montague, 1974; Cooper, 1983) employ formu- las of higher-order logic to derive semantic rep- resentations compositionally; then � -reduction is applied to simplify these representations. When the input sentence is ambiguous, these approaches require all readings to be enumerated and � - reduced individually. For large numbers of read- ings, this is both inefficient and unelegant. Existing underspecification approaches (Reyle, 1993; van Deemter and Peters, 1996; Pinkal, 1996; Bos, 1996) provide a partial solution to this problem. They delay the enumeration of the read- ings and represent them all at once in a single, compact description. An underspecification for- malism that is particularly well suited for describ- ing higher-order formulas is the Constraint Lan- guage for Lambda Structures, CLLS (Egg et al., 2001; Erk et al., 2001). CLLS descriptions can be derived compositionally and have been used to deal with a rich class of linguistic phenomena (Koller et al., 2000; Koller and Niehren, 2000). They are based on dominance constraints (Mar- cus et al., 1983; Rambow et al., 1995) and extend them with parallelism (Erk and Niehren, 2000) and binding constraints. However, lifting � -reduction to an operation on underspecified descriptions is not trivial, and to our knowledge it is not known how this can be done. Such an operation – which we will call un- derspecified � -reduction – would essentially � - reduce all described formulas at once by deriv- ing a description of the reduced formulas. In this paper, we show how underspecified � -reductions can be performed in the framework of CLLS. Our approach extends the work presented in (Bodirsky et al., 2001), which defines � -reduction constraints and shows how to obtain a complete solution procedure by reducing them to paral- lelism constraints in CLLS. The problem with this previous work is that it is often necessary to perform local disambiguations. Here we add a new mechanism which, for a large class of de- scriptions, permits us to perform underspecified � -reduction steps without disambiguating, and is still complete for the general problem. Plan. We start with a few examples to show what underspecified � -reduction should do, and why it is not trivial. We then introduce CLLS and � -reduction constraints. In the core of the paper we present a procedure for underspecified � -reduction and apply it to illustrative examples. 2 Examples In this section, we show what underspecified � - reduction should …

Content truncated to 500 words