Back to Search
Start Over
Dependency Parsing Schemata and Mildly Non-Projective Dependency Parsing.
- Source :
-
Computational Linguistics . Sep2011, Vol. 37 Issue 3, p541-586. 46p. - Publication Year :
- 2011
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08912017
- Volume :
- 37
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Computational Linguistics
- Publication Type :
- Academic Journal
- Accession number :
- 69934052