as a reference to a single attribute–value pair Each entity in the domain can be characterised as a set of attribute–value pairs for example type, dog, gender, female or age, 10 years. The problem then is defined as follows: Let be the intended referent, and be the contrast set. Then, a set of attribute–value pairs will represent a distinguishing description if the following two conditions hold: Every attribute–value pair in applies to : that is, every element of specifies an attribute–value that possesses. For every member of , there is at least one element of that does not apply to : that is, there is an in that specifies an attribute–value that does not possess. is said to rule out . In other words, to generate a referring expression one is looking for a set of properties that apply to the referent but not to the distractors. The problem could be easily solved by conjoining all the properties of the referent which often leads to long descriptions violating the second Gricean Maxim of Quantity. Another approach would be to find the shortest distinguishing description like the Full Brevity algorithm does. Yet in practice it is most common to instead include the condition that referring expressions produced by an algorithm should be as similar to human-produced ones as possible although this is often not explicitly mentioned. Basic algorithms Full Brevity The Full Brevity algorithm always finds a minimal distinguishing description meaning there is no shorter distinguishing description in regard to properties used. Therefore, it iterates over and checks every description of a length of properties until a distinguishing description is found. Two problems arise from this way of creating referring expressions. Firstly the algorithm has a high complexity meaning it is NP-hard which makes it impractical to use. Secondly human speakers produce descriptions that are not minimal in many situations. Greedy Heuristics The Greedy Heuristics algorithm approximates the Full Brevity algorithm by iteratively adding the most distinguishing property to the description. The most distinguishing property means the property that rules out most of the remaining distractors. The Greedy Heuristics algorithm is more efficient than the Full Brevity algorithm. Dale and Reiter(1995) present the following algorithm for the Greedy Heuristic: Let be the set of properties to be realised in our description; let be the set of properties known to be true of our intended referent (we assume that is non-empty); and