I&C Journal 1993 Journal Article
The Anaphora Problem
- E.S. Ristad
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.