Bibliographic Details
| Title: |
Splittability of Bilexical Context-Free Grammars is Undecidable. |
| Authors: |
Nederhof, Mark-Jan1 markjan.nederhof@gmail.com, Satta, Giorgio2 satta@dei.unipd.it |
| Source: |
Computational Linguistics. Sep2011, Vol. 37 Issue 3, Special section p1-23. 23p. |
| Subjects: |
Linguistic String Parser (Computer grammar), Lexical-functional grammar, Lexicon, Parsing (Grammar), Content analysis, Document style semantics & specification language, Corpora |
| Abstract: |
Bilexical context-free grammars (2-LCFGs) have proved to be accurate models for statistical natural language parsing. Existing dynamic programming algorithms used to parse sentences under these models have running time of O(|w|4), where w is the input string. A 2-LCFG is splittable if the left arguments of a lexical head are always independent of the right arguments, and vice versa. When a 2-LCFGs is splittable, parsing time can be asymptotically improved to O(|w|³). Testing this property is therefore of central interest to parsing efficiency. However, in this article we show the negative result that splittability of 2-LCFGs is undecidable. [ABSTRACT FROM AUTHOR] |
|
Copyright of Computational Linguistics is the property of MIT Press and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
