if C = ∅ then return L endif return failure Evaluation of REG systems Before 2000 evaluation of REG systems has been of theoretical nature like the one done by Dale and Reiter. More recently, empirical studies have become popular which are mostly based on the assumption that the generated expressions should be similar to human-produced ones. Corpus-based evaluation began quite late in REG due to a lack of suitable data sets. Still corpus-based evaluation is the most dominant method at the moment though there is also evaluation by human judgement. Corpus-based evaluation First the distinction between text corpora and experimental corpora has to be made. Text corpora like the GNOME corpus can contain texts from all kind of domains. In REG they are used to evaluate the realization part of algorithms. The content selection part of REG on the other hand requires a corpus that contains the properties of all domain objects as well as the properties used in references. Typically those fully "semantically transparent" created in experiments using simple and controlled settings. These experimental corpora once again can be separated into General-Purpose Corpora that were collected for another purpose but have been analysed for referring expressions and Dedicated Corpora that focus specifically on referring expressions. Examples of General-Purpose Corpora are the Pear Stories, the Map Task corpus or the Coconut corpus while the Bishop corpus, the Drawer corpus and the TUNA corpus count to the Dedicated Corpora. The TUNA corpus which contains web-collected data on the two domains furniture and people has been used in three shared REG challenges already. Evaluation metrics To measure the correspondence between corpora and the results of REG algorithms several Metrics have been developed. To measure the content selection part the Dice coefficient or the MASI (Measuring Agreement on Set-valued Items) metric are used. These measure the overlap of properties in two descriptions. In an evaluation the scores are usually averaged over references made by different human participants in the corpus. Also sometimes a measure called Perfect Recall Percentage (PRP) or Accuracy is used which calculates the percentage of perfect matches between an algorithm-produced and a human-produced reference. For the linguistic realization part of REG the overlap between strings has been measured using metrics like BLEU or NIST. A problem that occurs with string-based metrics is that for example "The small monkey" is measured closer to "The small donkey" than to "The little