This paper examines the problem of generating appropriate referring expressions in natural language generation, focusing on computational, algorithmic, and pragmatic issues. The goal is to generate definite noun phrases that successfully identify the intended referent to the hearer without conveying false conversational implicatures. The authors review several computational interpretations of the Gricean maxims of conversational implicature, with varying computational costs, and argue that the simplest may be the best, as it seems closest to what human speakers do. They describe their recommended algorithm in detail, along with the resources a host system must provide to use it, and an implementation used in the natural language generation component of the IDAS system. The paper discusses the issues involved in generating referring expressions, including the need to satisfy the referential communicative goal, avoid false implicatures, and ensure computational efficiency. It reviews previous work on generating referring expressions, including the work of Appelt and Kronfeld, and highlights the importance of distinguishing descriptions in identifying the intended referent. The authors also discuss the role of hearer models and the need to consider the hearer's knowledge and perceptual abilities when generating referring expressions. The paper evaluates different computational interpretations of the Gricean maxims, including the Full Brevity Interpretation, the Greedy Heuristic Interpretation, the Local Brevity Interpretation, and the Incremental Algorithm Interpretation. The authors argue that the Incremental Algorithm Interpretation is closest to what human speakers do, as it allows for incremental generation of referring expressions and is computationally efficient. They also discuss psychological evidence suggesting that human speakers often include unnecessary modifiers in their referring expressions, which may not lead to false implicatures. The paper concludes that while computational interpretations of the Gricean maxims are important, the behavior of human speakers may provide a more practical approach to generating referring expressions.This paper examines the problem of generating appropriate referring expressions in natural language generation, focusing on computational, algorithmic, and pragmatic issues. The goal is to generate definite noun phrases that successfully identify the intended referent to the hearer without conveying false conversational implicatures. The authors review several computational interpretations of the Gricean maxims of conversational implicature, with varying computational costs, and argue that the simplest may be the best, as it seems closest to what human speakers do. They describe their recommended algorithm in detail, along with the resources a host system must provide to use it, and an implementation used in the natural language generation component of the IDAS system. The paper discusses the issues involved in generating referring expressions, including the need to satisfy the referential communicative goal, avoid false implicatures, and ensure computational efficiency. It reviews previous work on generating referring expressions, including the work of Appelt and Kronfeld, and highlights the importance of distinguishing descriptions in identifying the intended referent. The authors also discuss the role of hearer models and the need to consider the hearer's knowledge and perceptual abilities when generating referring expressions. The paper evaluates different computational interpretations of the Gricean maxims, including the Full Brevity Interpretation, the Greedy Heuristic Interpretation, the Local Brevity Interpretation, and the Incremental Algorithm Interpretation. The authors argue that the Incremental Algorithm Interpretation is closest to what human speakers do, as it allows for incremental generation of referring expressions and is computationally efficient. They also discuss psychological evidence suggesting that human speakers often include unnecessary modifiers in their referring expressions, which may not lead to false implicatures. The paper concludes that while computational interpretations of the Gricean maxims are important, the behavior of human speakers may provide a more practical approach to generating referring expressions.