Complexity of Human Language Comprehension
Abstract
The goal of this research has been to understand the computational structure of principle-and-parameter linguistic theories: what computational problems do these theories pose and what is the underlying structure of those computations? To do this, I have analyzed the computational problem of human language comprehension: what linguistic representation is assigned to a given sound? This language comprehension problem may be factored into smaller, interrelated (but independently stable) problems defined on partial phonological, morphological, and syntactic representations. For example, in order to understand a given sound, the listener must assign a phonetic form to the sound; determine the morphemes that compose the words in the sound; and calculate the linguistic antecedent of every pronoun in the utterance. The author proves that these and some other subproblems are all NP-hard, and that language comprehension is itself PSPACE-hard, according to current linguistic theory. Keywords: Natural language.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1988
- Accession Number
- ADA214591
Entities
People
- Eric S. Ristad
Organizations
- Massachusetts Institute of Technology