let be the set of distractors (the contrast set). The initial conditions are thus as follows: all distractors; all properties true of ; In order to describe the intended referent with respect to the contrast set , we do the following: 1. Check Success: if then return as a distinguishing description elseif then fail else goto Step 2. 2. Choose Property: for each do: Chosen property is , where is the smallest set. goto Step 3. 3. Extend Description (wrt the chosen ): goto Step 1. Incremental Algorithm The Incremental Algorithm (IA) by Dale and Reiter was the most influential algorithm before 2000. It is based on the idea of a preferential order of attributes or properties that speakers go by. So in order to run the Incremental Algorithm, first a preference order of attributes has to be given. Now the algorithm follows that order and adds those properties to the description which rule out any remaining distractors. Furthermore, Dale and Reiter stress the attribute type which is always included in their descriptions even if it does not rule out any distractors. Also the type values are part of a subsumption hierarchy including some basic level values. For example, in the pet domain chihuahua is subsumed by dog and dog by animal. Because dog is defined as a basic level dog would be preferred by the algorithms, if chihuahua does not rule out any distractors. The Incremental Algorithm is easy to implement and also computationally efficient running in polynomial time. The description generated by the IA can contain redundant properties that are superfluous because of later added properties. The creators do not consider this as a weakness, but rather as making the expressions less "psycholinguistically implausible". The following algorithm is a simplified version of Dale and Reiter's Incremental Algorithm by Krahmer and van Deemter that takes as input the referent r, the D containing a collection of domain objects and a domain-specific ordered list Pref of preferred attributes. In the notation L is the description, C the context set of distractors and the function RulesOut() returns the set of objects which have a value different to V for attribute Ai. IncrementalAlgorithm ({r}, D, Pref) L ← ∅ C ← D - {r} for each Ai in list Pref do V = Value(r, Ai) if C ∩ RulesOut() ≠ ∅ then L ← L ∪ C ← C - RulesOut() endif