Underspecification formalisms: Hole semantics as dominance constraints

Bridging the Gap Between Underspecification Formalisms: Hole Semantics as Dominance Constraints Alexander Koller� Joachim Niehren�Stefan Thater koller@coli.uni - sb.de niehren@ps.uni - sb.de stth@coli.uni - sb.de Saarland University, Saarbriicken, Germany Abstract We define a back-and-forth translation between Hole Semantics and dominance constraints, two formalisms used in un- derspecified semantics. There are funda- mental differences between the two, but we show that they disappear on practi- cally useful descriptions. Our encoding bridges a gap between two underspeci- fication formalisms, and speeds up the processing of Hole Semantics. 1 Introduction In the past few years there has been consider- able activity in the development of formalisms for underspecified semantics (Alshawi and Crouch, 1992; Reyle, 1993; Bos, 1996; Copestake et al., 1999; Egg et al., 2001). These approaches all aim at controlling the combinatorial explosion of read- ings of sentences with multiple ambiguities. The common idea is to delay the enumeration of all readings for as long as possible. Instead, they work with a compact underspecified representation for as long as possible, only enumerating readings from this representation by need. At first glance, many of these formalisms seem to be very similar to each other. Now the ques- tion arises how deep this similarity is — are all underspecification formalisms basically the same? This paper answers this question for Hole Se- mantics and normal dominance constraints, two logical formalisms used in scope underspecifica- tion, by defining a back-and-forth translation be- tween the two. Due to fundamental differences in the way the two formalisms interpret under- specified descriptions, this encoding is only cor- rect in a nonstandard sense. However, we identify a class of chain-connected underspecified repre- sentations for which these differences disappear, and the encoding becomes correct. We conjecture that all linguistically useful descriptions are chain- connected. To support this claim, we prove that all descriptions generated by a nontrivial grammar we define are indeed chain-connected. Our results are interesting because it is the first time in the literature that two practically relevant underspecification formalisms are formally related to each other. In addition, the satisfi ability prob- lems of Hole Semantics and normal dominance constraints coincide on their chain-connected frag- ments. This means that satisfiability of Hole Se- mantics, which is NP-complete in general (Al- thaus et al., 2003), becomes polynomial in prac- tice, and can be checked using the efficient algo- rithms available for normal dominance constraints (Erk et al., 2002). Enumeration of readings be- comes much more efficient accordingly. 2 Some Intuitions The similarity of Hole Semantics and dominance constraints is illustrated in Fig. 1. The pictures graphically represent the underspecified represen- tations of all five readings of the sentence "Every researcher of a company saw a sample" in Hole Semantics (Bos, 1996) and as a dominance con- straint (Egg et al., 2001). The underspecified rep- resentations specify the material that every reading is made up of and constraints on the way in which they can be combined in obviously similar ways. However, the interpretations of these under- specified representations differ. In …

Content truncated to 500 words