Name
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â聢拢3). Testing this property is therefore of central interest to parsing efficiency. In this article, however, we show the negative result that splittability of 2-LCFGs is undecidable. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1162/COLI_a_00079 | Computational Linguistics |
Keywords | Field | DocType |
accurate model,bilexical context-free grammar,parsing efficiency,statistical natural language parsing,parsing time,lexical head,input string,central interest,left argument,dynamic programming,natural language processing,dynamic programming algorithm,context free grammar | Top-down parsing,L-attributed grammar,Context-free grammar,S-attributed grammar,Computer science,Bottom-up parsing,Parsing expression grammar,Artificial intelligence,Natural language processing,Parser combinator,Parsing | Journal |
Volume | Issue | ISSN |
37 | 4 | 0891-2017 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark-jan Nederhof | 1 | 387 | 53.30 |
| Giorgio Satta | 2 | 902 | 90.85 |