Projectivity

A dependency arc from a head word h to a dependent word d is projective if and only if all words linearly positioned between h and d are also descendants of h in the dependency tree. A tree is fully projective if every one of its arcs satisfies this condition. This property ensures that the tree can be drawn in the half-plane above the sentence without any crossing edges, preserving a planar graph structure that simplifies both parsing algorithms and linguistic annotation.

A non-projective parse contains at least one crossing dependency, a phenomenon prevalent in languages with free word order and rich morphology. For example, in German subordinate clauses, the verb appears at the end while its arguments may be scattered, creating crossing arcs. Similarly, wh-movement in English ('What did you see?') can produce non-projective structures. Parsers restricted to projective trees, such as basic transition-based models, systematically fail on these constructions, necessitating specialized algorithms like the Chu-Liu/Edmonds maximum spanning tree approach.

Standard arc-eager and arc-standard shift-reduce parsers are inherently limited to producing only projective trees because they build dependencies incrementally from left to right without the ability to create arcs that skip over unattached tokens. To handle non-projectivity, extensions like the swap-based algorithm introduce a SWAP transition that reorders the buffer, effectively linearizing crossing arcs. Alternatively, pseudo-projective parsing converts non-projective training trees into projective ones using specific encoding schemes, then decodes the output back to the original structure.

Graph-based parsers do not suffer from the projective constraint of transition-based systems. They score all possible arcs in a sentence simultaneously and decode the optimal tree using the Chu-Liu/Edmonds algorithm, which finds the maximum spanning tree in a directed graph. This algorithm naturally handles non-projective structures without special extensions, making graph-based methods the default choice for parsing languages with frequent crossing dependencies. The trade-off is computational complexity: O(n²) for arc-factored models versus O(n) for greedy transition-based parsing.

The gap degree of a dependency tree quantifies its deviation from projectivity. A gap occurs when a discontinuity in the projection of a node interrupts the linear span of its descendants. The maximum number of such discontinuities across all nodes defines the tree's gap degree. A projective tree has a gap degree of 0. Well-nestedness is a related constraint: a tree is well-nested if no two disjoint subtrees interleave. These metrics are used to characterize the syntactic complexity of treebanks and to design parsers with bounded non-projectivity handling.

The Universal Dependencies (UD) framework annotates both projective and non-projective structures, with the CoNLL-U format capturing the linear order and head indices necessary to reconstruct crossing arcs. UD treebanks reveal significant cross-linguistic variation: languages like English and French exhibit low non-projectivity rates, while Czech, Dutch, and Ancient Greek have substantially higher proportions. This variation directly impacts parser evaluation, as the Labeled Attachment Score (LAS) often drops on non-projective arcs, motivating the use of enhanced dependency representations.

In interrogative sentences, a wh-word (who, what, which) is fronted to the beginning of the clause while maintaining a syntactic dependency with its governing verb deeper in the sentence. This long-distance dependency creates a crossing arc over intervening words.

• Example: "What did you say that John bought?" — What depends on bought, crossing over the subject and auxiliary verbs.
• Common in English, German, and other languages with syntactic movement.
• Requires the parser to link a fronted constituent to a gap position far to the right.

Morphologically rich languages like Latin, Turkish, and Japanese permit flexible constituent ordering because grammatical roles are marked by case inflection rather than position. This scrambling frequently produces non-projective structures.

• Example (Latin): "Puer puellam vidit" and "Puellam puer vidit" both mean "The boy saw the girl."
• Discontinuous noun phrases where modifiers are separated from their heads are common.
• Parsers trained on fixed-word-order languages like English often fail catastrophically on these constructions.

A syntactic phenomenon where a heavy constituent, typically a relative clause or complement clause, is shifted to the right edge of the sentence, separating it from the noun it modifies. This rightward movement creates a non-projective arc.

• Example: "A woman arrived who was wearing a red hat." — who was wearing a red hat modifies woman, but the verb arrived intervenes.
• Common in English and Germanic languages for stylistic or processing reasons.
• The dependent appears linearly after material that is structurally higher in the tree.

In subject control and subject-to-subject raising constructions, a nominal element serves as the syntactic subject of a matrix verb while functioning as the semantic argument of an embedded verb. This dual role can force non-projective arcs in surface syntax representations.

• Example (Raising): "John seems to be happy." — John is the syntactic subject of seems but the semantic subject of happy.
• Example (Control): "Mary promised to leave." — Mary controls the unexpressed subject of to leave.
• Enhanced dependency representations explicitly add these arcs.

In languages like German and Dutch, modifiers of a noun can be separated from their head by intervening verbal material, particularly in verb-final clauses. This creates a crossing dependency where the determiner and noun are not adjacent.

• Example (German): "Ich habe den Mann gestern gesehen, der den Hut trug." — den Mann and der den Hut trug form a discontinuous constituent.
• Driven by the interaction of the verbal complex and the nominal phrase.
• Requires parsers to handle long-range attachment across clause boundaries.

In Romance languages like Spanish and Italian, a pronominal clitic that semantically belongs to an embedded infinitive can attach syntactically to a higher matrix verb. This restructuring creates a non-projective dependency between the clitic and the embedded verb.

• Example (Spanish): "Lo quiero ver." ("I want to see it.") — Lo attaches to quiero but is the object of ver.
• The clitic moves leftward across the matrix verb, crossing syntactic boundaries.
• Challenges parsers that assume strict locality between a verb and its arguments.