GPSG-Recognition is NP-Hard
Proponents of generalized phrase structure grammar (GPSG) cite its weak context-free generative power as proof of the computational tractability of GPSG-Recognition. Since context-free languages (CFLs) can be parsed in time proportional to the cube of the sentence length, and GPSGs only genera...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/5615 |
| _version_ | 1826196839383171072 |
|---|---|
| author | Ristad, Eric Sven |
| author_facet | Ristad, Eric Sven |
| author_sort | Ristad, Eric Sven |
| collection | MIT |
| description | Proponents of generalized phrase structure grammar (GPSG) cite its weak context-free generative power as proof of the computational tractability of GPSG-Recognition. Since context-free languages (CFLs) can be parsed in time proportional to the cube of the sentence length, and GPSGs only generate CFLs, it seems plausible the GPSGs can also be parsed in cubic time. This longstanding, widely assumed GPSG "efficient parsability" result in misleading: parsing the sentences of an arbitrary GPSG is likely to be intractable, because a reduction from 3SAT proves that the universal recognition problem for the GPSGs of Gazdar (1981) is NP-hard. Crucially, the time to parse a sentence of a CFL can be the product of sentence length cubed and context-free grammar size squared, and the GPSG grammar can result in an exponentially large set of derived context-free rules. A central object in the 1981 GPSG theory, the metarule, inherently results in an intractable parsing problem, even when severely constrained. The implications for linguistics and natural language parsing are discussed. |
| first_indexed | 2024-09-23T10:38:25Z |
| id | mit-1721.1/5615 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:38:25Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/56152019-04-12T08:26:40Z GPSG-Recognition is NP-Hard Ristad, Eric Sven GPSG parsing complexity natural language linguistics snatural language parsing Proponents of generalized phrase structure grammar (GPSG) cite its weak context-free generative power as proof of the computational tractability of GPSG-Recognition. Since context-free languages (CFLs) can be parsed in time proportional to the cube of the sentence length, and GPSGs only generate CFLs, it seems plausible the GPSGs can also be parsed in cubic time. This longstanding, widely assumed GPSG "efficient parsability" result in misleading: parsing the sentences of an arbitrary GPSG is likely to be intractable, because a reduction from 3SAT proves that the universal recognition problem for the GPSGs of Gazdar (1981) is NP-hard. Crucially, the time to parse a sentence of a CFL can be the product of sentence length cubed and context-free grammar size squared, and the GPSG grammar can result in an exponentially large set of derived context-free rules. A central object in the 1981 GPSG theory, the metarule, inherently results in an intractable parsing problem, even when severely constrained. The implications for linguistics and natural language parsing are discussed. 2004-10-01T20:17:11Z 2004-10-01T20:17:11Z 1985-03-01 AIM-837 http://hdl.handle.net/1721.1/5615 en_US AIM-837 11 p. 3087711 bytes 2405273 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | GPSG parsing complexity natural language linguistics snatural language parsing Ristad, Eric Sven GPSG-Recognition is NP-Hard |
| title | GPSG-Recognition is NP-Hard |
| title_full | GPSG-Recognition is NP-Hard |
| title_fullStr | GPSG-Recognition is NP-Hard |
| title_full_unstemmed | GPSG-Recognition is NP-Hard |
| title_short | GPSG-Recognition is NP-Hard |
| title_sort | gpsg recognition is np hard |
| topic | GPSG parsing complexity natural language linguistics snatural language parsing |
| url | http://hdl.handle.net/1721.1/5615 |
| work_keys_str_mv | AT ristadericsven gpsgrecognitionisnphard |