Complexity of Human Language Comprehension
MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB
Pagination or Media Count:
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.