The Anaphora Problem

Consider the computational problem of understanding the utterances of a human language that contain pronouns. In order to completely understand such utterances, the language user must determine the intended reference of each pronoun in a given utterance. For example, in order to comprehend the English sentence Jocasta loved her son, the hearer might determine that the possessive pronoun her and the proper noun Jocasta both refer to Jocasta, the Queen of Thebes. Using such facts of linguistic knowledge, we develop a sophisticated formal model of this computational problem and prove that it is NP-complete. No knowledge of linguistic theory is needed to understand our analysis, only knowledge of English.

Authors

• E.S. Ristad

Keywords

No keywords are indexed for this paper.