The anaphora problem
type: Item
instance of: scholarly article
title: The anaphora problem
zbMATH Open document ID: 0776.68099
author: Eric Sven Ristad
published in: Information and Computation
publication date: 1993-08-30T00:00:00Z
review text: 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 references of each pronoun in a given utterances. 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. This result is the first empirically-plausible bound on the computational complexity of human language. No knowledge of linguistic theory is needed to understand our analysis, only knowledge of English.
Mathematics Subject Classification ID: 68T50
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 370448
zbMATH Keywords: NP-complete
zbMATH Keywords: computational complexity of human language
MaRDI profile type: Publication
full work available at URL: inco.1993.1042
OpenAlex ID: W2072168443
DOI: 10.1006/INCO.1993.1042
Recommended article: Q2763101
Recommended article: Anaphora and Discourse Structure
Recommended article: Q4783609
Recommended article: Anaphors and Quantifiers
Recommended article: Q2762870
Recommended article: The problem of reasoning by analogy
Recommended article: Anaphora resolution. Algorithms, resources, and applications
description: scientific article; zbMATH DE number 370448