Computational Consequences of Agreement and Ambiguity in Natural Language
The computer science technique of computational complexity analysis can provide powerful insights into the algorithm-neutral analysis of information processing tasks. Here we show that a simple, theory-neutral linguistic model of syntactic agreement and ambiguity demonstrates that natural langu...
| Main Authors: | , |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/6526 |
| _version_ | 1811070252402868224 |
|---|---|
| author | Ristad, Eric Sven Berwick, Robert C. |
| author_facet | Ristad, Eric Sven Berwick, Robert C. |
| author_sort | Ristad, Eric Sven |
| collection | MIT |
| description | The computer science technique of computational complexity analysis can provide powerful insights into the algorithm-neutral analysis of information processing tasks. Here we show that a simple, theory-neutral linguistic model of syntactic agreement and ambiguity demonstrates that natural language parsing may be computationally intractable. Significantly, we show that it may be syntactic features rather than rules that can cause this difficulty. Informally, human languages and the computationally intractable Satisfiability (SAT) problem share two costly computional mechanisms: both enforce agreement among symbols across unbounded distances (Subject-Verb agreement) and both allow ambiguity (is a word a Noun or a Verb?). |
| first_indexed | 2024-09-23T08:33:32Z |
| id | mit-1721.1/6526 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:33:32Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/65262019-04-09T18:27:03Z Computational Consequences of Agreement and Ambiguity in Natural Language Ristad, Eric Sven Berwick, Robert C. The computer science technique of computational complexity analysis can provide powerful insights into the algorithm-neutral analysis of information processing tasks. Here we show that a simple, theory-neutral linguistic model of syntactic agreement and ambiguity demonstrates that natural language parsing may be computationally intractable. Significantly, we show that it may be syntactic features rather than rules that can cause this difficulty. Informally, human languages and the computationally intractable Satisfiability (SAT) problem share two costly computional mechanisms: both enforce agreement among symbols across unbounded distances (Subject-Verb agreement) and both allow ambiguity (is a word a Noun or a Verb?). 2004-10-04T15:14:41Z 2004-10-04T15:14:41Z 1988-11-01 AIM-1178 http://hdl.handle.net/1721.1/6526 en_US AIM-1178 2889628 bytes 1140647 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Ristad, Eric Sven Berwick, Robert C. Computational Consequences of Agreement and Ambiguity in Natural Language |
| title | Computational Consequences of Agreement and Ambiguity in Natural Language |
| title_full | Computational Consequences of Agreement and Ambiguity in Natural Language |
| title_fullStr | Computational Consequences of Agreement and Ambiguity in Natural Language |
| title_full_unstemmed | Computational Consequences of Agreement and Ambiguity in Natural Language |
| title_short | Computational Consequences of Agreement and Ambiguity in Natural Language |
| title_sort | computational consequences of agreement and ambiguity in natural language |
| url | http://hdl.handle.net/1721.1/6526 |
| work_keys_str_mv | AT ristadericsven computationalconsequencesofagreementandambiguityinnaturallanguage AT berwickrobertc computationalconsequencesofagreementandambiguityinnaturallanguage |