Abstract
We consider the problem of parsing non-recursive context-free grammars, i.e., context-free grammars that generate finite languages. In natural language processing, this problem arises in several areas of application, including natural language generation, speech recognition and machine translation. We present two tabular algorithms for parsing of non-recursive context-free grammars, and show that they perform well in practical settings, despite the fact that this problem is PSPACE-complete.
| Original language | English |
|---|---|
| Title of host publication | 40TH ANNUAL MEETING OF THE ASSOCIATION FOR COMPUTATIONAL LINGUISTICS, PROCEEDINGS OF THE CONFERENCE |
| Place of Publication | SOMERSET |
| Publisher | Association for Computational Linguistics (ACL) |
| Pages | 112-119 |
| Number of pages | 8 |
| ISBN (Print) | 1-55860-883-4 |
| Publication status | Published - 2002 |
| Event | 40th Annual Meeting of the Association-for-Computational-Linguistics - , Panama Duration: 7-Jul-2002 → 12-Jul-2002 |
Other
| Other | 40th Annual Meeting of the Association-for-Computational-Linguistics |
|---|---|
| Country/Territory | Panama |
| Period | 07/07/2002 → 12/07/2002 |