Computational Structure of Human Language
The central thesis of this report is that human language is NP-complete. That is, the process of comprehending and producing utterances is bounded above by the class NP, and below by NP-hardness. This constructive complexity thesis has two empirical consequences. The first is to predict that a...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/7038 |
| _version_ | 1811092250666467328 |
|---|---|
| author | Ristad, Eric Sven |
| author_facet | Ristad, Eric Sven |
| author_sort | Ristad, Eric Sven |
| collection | MIT |
| description | The central thesis of this report is that human language is NP-complete. That is, the process of comprehending and producing utterances is bounded above by the class NP, and below by NP-hardness. This constructive complexity thesis has two empirical consequences. The first is to predict that a linguistic theory outside NP is unnaturally powerful. The second is to predict that a linguistic theory easier than NP-hard is descriptively inadequate. To prove the lower bound, I show that the following three subproblems of language comprehension are all NP-hard: decide whether a given sound is possible sound of a given language; disambiguate a sequence of words; and compute the antecedents of pronouns. The proofs are based directly on the empirical facts of the language user's knowledge, under an appropriate idealization. Therefore, they are invariant across linguistic theories. (For this reason, no knowledge of linguistic theory is needed to understand the proofs, only knowledge of English.) To illustrate the usefulness of the upper bound, I show that two widely-accepted analyses of the language user's knowledge (of syntactic ellipsis and phonological dependencies) lead to complexity outside of NP (PSPACE-hard and Undecidable, respectively). Next, guided by the complexity proofs, I construct alternate linguisitic analyses that are strictly superior on descriptive grounds, as well as being less complex computationally (in NP). The report also presents a new framework for linguistic theorizing, that resolves important puzzles in generative linguistics, and guides the mathematical investigation of human language. |
| first_indexed | 2024-09-23T15:15:10Z |
| id | mit-1721.1/7038 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:15:10Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/70382019-04-10T11:52:22Z Computational Structure of Human Language Ristad, Eric Sven The central thesis of this report is that human language is NP-complete. That is, the process of comprehending and producing utterances is bounded above by the class NP, and below by NP-hardness. This constructive complexity thesis has two empirical consequences. The first is to predict that a linguistic theory outside NP is unnaturally powerful. The second is to predict that a linguistic theory easier than NP-hard is descriptively inadequate. To prove the lower bound, I show that the following three subproblems of language comprehension are all NP-hard: decide whether a given sound is possible sound of a given language; disambiguate a sequence of words; and compute the antecedents of pronouns. The proofs are based directly on the empirical facts of the language user's knowledge, under an appropriate idealization. Therefore, they are invariant across linguistic theories. (For this reason, no knowledge of linguistic theory is needed to understand the proofs, only knowledge of English.) To illustrate the usefulness of the upper bound, I show that two widely-accepted analyses of the language user's knowledge (of syntactic ellipsis and phonological dependencies) lead to complexity outside of NP (PSPACE-hard and Undecidable, respectively). Next, guided by the complexity proofs, I construct alternate linguisitic analyses that are strictly superior on descriptive grounds, as well as being less complex computationally (in NP). The report also presents a new framework for linguistic theorizing, that resolves important puzzles in generative linguistics, and guides the mathematical investigation of human language. 2004-10-20T20:23:14Z 2004-10-20T20:23:14Z 1990-10-01 AITR-1260 http://hdl.handle.net/1721.1/7038 en_US AITR-1260 12779840 bytes 8930965 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Ristad, Eric Sven Computational Structure of Human Language |
| title | Computational Structure of Human Language |
| title_full | Computational Structure of Human Language |
| title_fullStr | Computational Structure of Human Language |
| title_full_unstemmed | Computational Structure of Human Language |
| title_short | Computational Structure of Human Language |
| title_sort | computational structure of human language |
| url | http://hdl.handle.net/1721.1/7038 |
| work_keys_str_mv | AT ristadericsven computationalstructureofhumanlanguage |