Presents four computational interpretations of the Gricean conversational maxims in the generation of referring expressions: (1) full brevity interpretation; (2) greedy heuristic interpretation; (3) local brevity interpretation; and (4) incremental interpretation. Examines problems involved in generating definite noun phrases that are appropriate referring expressions and describes the authors's algorithm for generating referring expressions. (Author/JMV)