Generating Minimal Definite Descriptions

Generating Minimal Definite Descriptions Claire Gardent CNRS, LORIA, Nancy gardent@loria.fr Abstract The incremental algorithm introduced in (Dale and Reiter, 1995) for producing dis- tinguishing descriptions does not always generate a minimal description. In this paper, I show that when generalised to sets of individuals and disjunctive proper- ties, this approach might generate unnec- essarily long and ambiguous and/or epis- temically redundant descriptions. I then present an alternative, constraint-based al- gorithm and show that it builds on existing related algorithms in that (i) it produces minimal descriptions for sets of individu- als using positive, negative and disjunctive properties, (ii) it straightforwardly gener- alises to n-ary relations and (iii) it is inte- grated with surface realisation. 1 Introduction In English and in many other languages, a possible function of definite descriptions is to identify a set of referents1: by uttering an expression of the form The N, the speaker gives sufficient information to the hearer so that s/he can identify the set of the objects the speaker is referring to. From the generation perspective, this means that, starting from the set of objects to be described and from the properties known to hold of these objects by both the speaker and the hearer, a definite de- scription must be constructed which allows the user 1The other well-known function of a definite is to inform the hearer of some specific attributes the referent of the NP has. to unambiguously identify the objects being talked about. While the task of constructing singular definite descriptions on the basis of positive properties has received much attention in the generation literature (Dale and Haddock, 1991; Dale and Reiter, 1995; Horacek, 1997; Krahmer et al., 2001), for a long time, a more general statement of the task at hand re- mained outstanding. Recently however, several pa- pers made a step in that direction. (van Deemter, 2001) showed how to extend the basic Dale and Re- iter Algorithm (Dale and Reiter, 1995) to generate plural definite descriptions using not just conjunc- tions of positive properties but also negative and disjunctive properties; (Stone, 1998) integrates the D&R algorithm into the surface realisation process and (Stone, 2000) extends it to deal with collective and distributive plural NPs. Notably, in all three cases, the incremental struc- ture of the D&R’s algorithm is preserved: the al- gorithm increments a set of properties till this set uniquely identifies the target set i.e., the set of ob- jects to be described. As (Garey and Johnson, 1979) shows, such an incremental algorithm while be- ing polynomial (and this, together with certain psy- cholinguistic observations, was one of the primary motivation for privileging this incremental strategy) is not guaranteed to find the minimal solution i.e., the description which uniquely identifies the target set using the smallest number of atomic properties. In this paper, I argue that this characteristic of the incremental algorithm while reasonably innocuous when generating singular definite descriptions using only conjunctions of positive properties, renders it Computational Linguistics (ACL), Philadelphia, July 2002, pp. 96-103. Proceedings …

Content truncated to 500 words