Viewing referring expression generation as search

Almost all natural language generation (NLG) systems are faced with the problem of the generation of referring expressions (GRE): given a symbol corresponding to an intended referent, how do we work out the semantic content of a referring expression that uniquely identifies the entity in question? This is now one of the most widely explored problems in NLG: over the last 15 years, a number of algorithms have been proposed for addressing different aspects of this problem, but the different approaches taken make it very difficult to compare and contrast the algorithms provided in any meaningful way. In this paper, we show how viewing the problem of referring expression generation as a search problem allows us to recast existing algorithms in a way that makes their similarities and differences clear.