Abstract

This paper presents a Conceptual Graph (CG) framework to the Generation of Referring Expressions (GRE). Employing Conceptual Graphs as the underlying formalism allows a rigorous, semantically rich, approach to GRE. A number of advantages over existing work are discussed. The new framework is also used to revisit existing complexity results in a fully rigorous way, showing that the expressive power of CGs does not increase the theoretical complexity of GRE