Dependency Parsing Schemata and Mildly Non-Projective Dependency Parsing

Abstract

We introduce dependency parsing schemata, a formal framework, based on Sikkel’s parsing
schemata for constituency parsers, that can be used to describe, analyze and compare dependency
parsing algorithms. We use this framework to describe several well-known projective and nonprojective
dependency parsers, build correctness proofs, and find formal relations between them.
We also illustrate how this framework can be applied to Link Grammar, a dependency-related
formalism. Finally, we 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(n^(5+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(n^(4+3k)).