Imagine drawing a sentence on a page and mapping its grammatical structure by drawing arrows (arcs) from each head word to its dependents. If you can draw all of these arcs above the sentence without any of them crossing, the sentence is projective. This neat, nested structure mirrors the familiar tree diagrams of context-free grammars.
However, human language is rarely so orderly. In languages with flexible word order like Hindi, Turkish, or Dutch—and even in English sentences involving extraposition or gapping—words that belong together syntactically are frequently separated by other phrases. When you draw the dependency arcs for these sentences, the lines inevitably cross. This phenomenon is known as non-projectivity. As noted by Ryan McDonald et al. in Multilingual Dependency Analysis with a Two-Stage Discriminative Parser, standard parsing algorithms that assume projectivity fail to capture these long-range, interleaved relationships, leading to structural inaccuracies.
The Computational Dilemma
Why not simply allow arcs to cross anywhere? The obstacle is computational tractability. Projective parsing can be done very efficiently (often in linear or cubic time) because it allows algorithms to use dynamic programming over contiguous spans of text. Once you allow unrestricted crossing arcs, the search space explodes. As Marco Kuhlmann et al. point out in Mildly Context-Sensitive Dependency Languages, unrestricted non-projective parsing quickly becomes an NP-hard problem.
To resolve this, researchers have developed three main paradigms: global graph-based optimization, label-encoding transformations, and extended transition systems.
Global Optimization: Parsing as a Maximum Spanning Tree
Instead of building a tree from the bottom up or left to right, what if we consider every possible dependency simultaneously? This is the core intuition behind graph-based non-projective parsing.
We can treat a sentence as a fully connected directed graph, where every word is a node and every possible directed edge has a weight representing the probability or score of that dependency. Finding the best parse tree then reduces to finding the Maximum Spanning Tree (MST) of this graph—a tree that connects all words with the highest possible total edge score.
Because the MST algorithm evaluates edges globally rather than relying on contiguous text spans, it naturally accommodates crossing arcs without any extra machinery. Ryan McDonald et al. demonstrated in Multilingual Dependency Analysis with a Two-Stage Discriminative Parser that this framework could robustly recover non-projective structures across diverse languages. To handle more complex, non-local features that a simple edge-factored model might miss, Keith B. Hall in K-best Spanning Tree Parsing extended this by generating the top $k$ candidate spanning trees first, then applying a sophisticated reranker to find the true syntactic structure.
Pseudo-Projective Parsing: Hiding Crossings in the Labels
If you already have a highly optimized, lightning-fast projective parser, you might want to avoid switching to a graph-based MST algorithm. Joakim Nivre et al. introduced a brilliant workaround in Labeled Pseudo-Projective Dependency Parsing with Support Vector Machines called pseudo-projective parsing.
The core idea is to temporarily "untangle" the non-projective tree before training:
- Projectivization (Training): If an arc crosses another, we lift the dependent up the tree, attaching it to a higher ancestor until the crossing disappears and the tree becomes projective. Crucially, we do not throw away the original structure; we encode the path of the lift directly into the dependency label (e.g., labeling an edge as
SBJ|VPto show it was lifted from a verb phrase). - Standard Parsing: A standard projective parser is trained and run on these modified trees.
- De-projectivization (Post-processing): At test time, the parser outputs a projective tree containing these enriched labels. A deterministic post-processing step reads the labels to "undo" the lifts, restoring the crossing arcs to their rightful positions.
This allows a simpler parser to successfully recover complex, non-projective linguistic structures simply by treating the geometry of crossing arcs as a labeling problem.
Transition Systems: Reordering and Non-Local Jumps
Transition-based parsers (like shift-reduce parsers) process sentences sequentially, maintaining a stack of partially processed words and a buffer of remaining words. Traditionally, they can only form dependencies between words that are adjacent on the stack, making non-projectivity impossible to parse.
To overcome this limitation without sacrificing the speed of transition systems, researchers introduced actions that dynamically reorder the input. One prominent approach is the SWAP transition, analyzed by Joakim Nivre et al. in An Improved Oracle for Dependency Parsing with Online Reordering and Miryam de Lhoneux et al. in Arc-Hybrid Non-Projective Dependency Parsing with a Static-Dynamic Oracle. When the parser encounters a crossing dependency, the SWAP action pops words off the stack and puts them back into the buffer. This changes the linear order of the words on the fly, allowing non-adjacent words to become adjacent so a dependency can be drawn between them.
Another approach is to abandon strict stack-based locality altogether. The Covington parsing algorithm allows the parser to look back through the entire history of words rather than just the top of the stack. Carlos Gómez-Rodríguez et al. designed an efficient dynamic oracle for this framework in An Efficient Dynamic Oracle for Unrestricted Non-Projective Parsing, allowing the parser to calculate optimal recovery paths even after making mistakes during training. To accelerate this process, Daniel Fernández-González et al. introduced non-local transitions in Non-Projective Dependency Parsing with Non-Local Transitions. Their system (NL-Covington) allows the parser to "jump" directly to non-local words in a single step, drastically reducing the number of operations required to resolve crossing arcs.
Taming Complexity via Mild Non-Projectivity
While unrestricted non-projectivity is computationally daunting, empirical evidence shows that human languages are not completely chaotic. Prashanth Mannem et al. analyzed treebanks in Insights into Non-projectivity in Hindi and found that while non-projectivity is frequent, it is "mildly" non-projective—adhering to specific graph constraints.
This linguistic reality aligns perfectly with formal grammar theory. As proven by Marco Kuhlmann et al. in Mildly Context-Sensitive Dependency Languages, by placing specific structural restrictions on how arcs can cross (such as limiting the "gap degree" or enforcing well-nestedness), non-projective dependency structures map exactly onto mildly context-sensitive grammar formalisms like Tree Adjoining Grammar (TAG). This mathematical bridge ensures that parsers can be designed to capture nearly all real-world crossing dependencies while guaranteeing polynomial-time efficiency.
Key Foundational Work
Pseudo-Projectivity, A Polynomially Parsable Non-Projective Dependency Grammar (1998) — contributed 2 concept elements to this direction.
Head Corner Parsing for Discontinuous Constituency (1991) — contributed 1 concept elements to this direction.
Segregatory Coordination and Ellipsis in Text Generation (1998) — contributed 1 concept elements to this direction.