Name
Abstract | ||
|---|---|---|
We study the problem of finding the best head-driven parsing strategy for Linear Context-Free Rewriting System productions. A head-driven strategy must begin with a specified righthand-side nonterminal (the head) and add the remaining nonterminals one at a time in any order. We show that it is NP-hard to find the best head-driven strategy in terms of either the time or space complexity of parsing. |
Year | Venue | Keywords |
|---|---|---|
2011 | ACL | specified righthand-side nonterminal,head-driven parsing strategy,linear context-free rewriting system,head-driven strategy,remaining nonterminals,linear context-free,space complexity,optimal head-driven |
Field | DocType | Volume |
Top-down parsing,Terminal and nonterminal symbols,Programming language,S-attributed grammar,Computer science,Bottom-up parsing,Natural language processing,Artificial intelligence,Rewriting,Parsing | Conference | P11-1 |
Citations | PageRank | References |
4 | 0.39 | 20 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pierluigi Crescenzi | 1 | 1002 | 95.31 |
| Daniel Gildea | 2 | 2269 | 193.43 |
| Andrea Marino | 3 | 185 | 23.48 |
| Gianluca Rossi | 4 | 235 | 21.60 |
| Giorgio Satta | 5 | 902 | 90.85 |