Name
Abstract | ||
|---|---|---|
We introduce dependency parsing schemata, a formal framework based on Sikkel's parsing schemata for constituency parsers, which can be used to describe, analyze, and compare dependency parsing algorithms. We use this framework to describe several well-known projective and non-projective dependency parsers, build correctness proofs, and establish formal relationships between them. We then use the framework to define new polynomial-time parsing algorithms for various mildly non-projective dependency formalisms, including well-nested structures with their gap degree bounded by a constant k in time O(n5+2k), and a new class that includes all gap degree k structures present in several natural language treebanks (which we call mildly ill-nested structures for gap degree k) in time O(n4+3k). Finally, we illustrate how the parsing schema framework can be applied to Link Grammar, a dependency-related formalism. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1162/COLI_a_00060 | Computational Linguistics |
Keywords | Field | DocType |
gap degree k structure,constant k,time o,gap degree,non-projective dependency parsing,gap degree k,non-projective dependency formalisms,non-projective dependency parsers,formal framework,parsing schema framework,parsing schema,polynomial time,natural language,dependency parsing | Top-down parsing language,Top-down parsing,Link grammar,S-attributed grammar,Computer science,Dependency grammar,Bottom-up parsing,Artificial intelligence,Natural language processing,Parsing,Parser combinator | Journal |
Volume | Issue | ISSN |
37 | 3 | 0891-2017 |
Citations | PageRank | References |
14 | 0.61 | 47 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carlos Gómez-Rodríguez | 1 | 347 | 41.18 |
| John Carroll | 2 | 1971 | 222.19 |
| David J. Weir | 3 | 840 | 83.84 |