This paper examines the problem of generating appropriate referring expressions, specifically definite noun phrases that identify the intended referent while avoiding false conversational implicatures. The authors review several computational interpretations of Grice's conversational implicature maxims, focusing on their computational costs and how well they approximate human behavior. They argue that the simplest interpretation, which is also the most computationally efficient, is the best approach. The paper describes an algorithm for generating referring expressions that meets these criteria, along with the domain knowledge resources required for its implementation. The algorithm is designed to be domain-independent and is implemented in the natural language generation component of the IDAS system. The authors also discuss the psychological evidence supporting their approach, noting that human speakers often include unnecessary modifiers in their referring expressions and can begin to utter a referring expression before completing the task. The paper concludes with a discussion of future research directions.This paper examines the problem of generating appropriate referring expressions, specifically definite noun phrases that identify the intended referent while avoiding false conversational implicatures. The authors review several computational interpretations of Grice's conversational implicature maxims, focusing on their computational costs and how well they approximate human behavior. They argue that the simplest interpretation, which is also the most computationally efficient, is the best approach. The paper describes an algorithm for generating referring expressions that meets these criteria, along with the domain knowledge resources required for its implementation. The algorithm is designed to be domain-independent and is implemented in the natural language generation component of the IDAS system. The authors also discuss the psychological evidence supporting their approach, noting that human speakers often include unnecessary modifiers in their referring expressions and can begin to utter a referring expression before completing the task. The paper concludes with a discussion of future research directions.