Dependency Syntax and Universal Dependencies › The Dependency Tree

A dependency structure is a labelled directed graph over the syntactic words of a sentence. Here we first define the basic-tree representation. Enhanced UD graphs, introduced later, need not be trees. The axioms are not arbitrary formalities. They are the conditions that guarantee the structure can be read as a hierarchy of heads and dependents, with no word belonging to two places at once and no word floating outside the sentence.

The nodes here are syntactic words, not necessarily whitespace-delimited strings or language-model subword pieces. UD can split an orthographic contraction into multiple syntactic words. It records inflectional morphology on the word rather than creating a node for every morpheme. The code below uses the name tokens for lists of syntactic-word records; it does not apply an LLM tokenizer. UD word segmentation defines that boundary.

Given a sentence with syntactic words $w_1, \ldots, w_n$, a dependency tree is a set of arcs

$$A \subseteq \{ (h, d, \ell) : h \in \{0, 1, \ldots, n\},\ d \in \{1, \ldots, n\},\ h \neq d,\ \ell \in \mathcal{L} \}$$

where $\mathcal{L}$ is a finite label set. The special index $0$ denotes the artificial root, a virtual node that sits above the sentence and has no word of its own. Every token $w_d$ has exactly one incoming arc, called its head arc: $h$ is the head and $d$ is the dependent.

The arc labels come from a closed vocabulary. In UD the core set has 37 universal relations, with language-specific subtypes permitted. A shared vocabulary supplies targets for supervised label learning and direct comparison. Unrelated one-off labels would require an additional mapping before they could serve those purposes. An inventory gives annotators shared categories; applying them consistently also requires definitions and construction-specific guidance.

For every word $d \in \{1, \ldots, n\}$, there must be exactly one incoming labelled arc $(h,d,\ell) \in A$, counting the head and label together. This is the single-head axiom, and it is a necessary condition for a basic dependency tree. It does not by itself exclude cycles or guarantee a single root.

The axiom rules out multi-parent structures in the basic tree. In She wants to leave, for example, She is the subject of wants in that tree, while an enhanced graph can also relate it to leave as an externally supplied subject. We will meet this enhanced dependency layer later. An ordinary fronted wh-object is different: in Who did you see?, Who can already be the obj dependent of see in the single-headed basic tree. No additional filler-to-specifier arc is part of that UD analysis. The basic tree gives parsers a well-defined object to predict and evaluators a well-defined object to score.

Exactly one token has head $0$. Call it the root $d_r$. The sentence root is typically its main predicate, which may be verbal or nonverbal. Ellipsis and fragments need construction-specific choices, including promotion when a predicate is missing.

Root selection is not always obvious. In She is a doctor the root is doctor (a predicate nominal), not is, because UD treats the copula as a dependent (cop). In Who came? the root is came even though who is prominent. In Hello! the root is Hello. Root selection affects the structural targets used for parser training. For two analyses of the same sentence with different roots, every root-to-leaf path begins with a different word; the remaining attachments need not all change. A parser trained under different root conventions may learn different structural priors.

The root also serves as the anchor for connectivity. Once the root is fixed, every other word must be reachable from it along head-to-dependent arcs. That requirement is what turns a collection of local head decisions into a single connected structure.

Two more axioms ensure the structure really is a tree:

• Acyclicity. No token is its own ancestor. Following head pointers from any token must terminate.
• Connectivity. Every word is reachable from artificial node 0 by following head-to-dependent arcs. Equivalently, following parent pointers from any word eventually reaches 0.

Connectivity follows from single-head plus acyclicity plus a finite sentence: if you follow heads from any token you cannot loop forever, so you eventually hit artificial node 0, the only node without an incoming arc. This argument assumes that every head index is a valid word index or 0. The extra requirement that exactly one word has head 0 is UD's sentence-root convention.

It is worth seeing why these conditions matter in practice. Without acyclicity, a parser could produce a cycle such as a heads b, b heads c, and c heads a. Such a structure has no natural root and cannot be drawn as a hierarchy. Without connectivity, a token could be attached to a head that is not connected to the rest of the sentence, producing a forest rather than a tree. UD treebanks are required to be connected, so a validation check for connectivity is a useful sanity check on any parser output.