nLab dependency grammar

 Idea

Dependency grammars are a kind of formal grammars based on the notion of dependency graph, rather than constituency trees. The first mathematical definitions are from Hays (1960) and Gaifman (1965).

Definition

A dependency grammar is a tuple $G = (V, X, R, s)$ where $V$ and $X$ are finite sets of terminal and non-terminal symbols with the start symbol $s \in X$ and a finite set of rules $R \subseteq \mathcal{R}_1 \cup \mathcal{R}_2 \cup \mathcal{R}_3$ which have one of the following shapes:

1. $\mathcal{R}_1 = X^\star \times X \times X^\star$. The interpretation of a rule $r = (u, x, v) \in \mathcal{R}_1$ is that a word of type $x \in X$ can govern words of type $u \in X^\star$ on its left and $v \in X^\star$ on its right. We say that $u$ and $v$ are the left and right dependencies of the head of type $x$.
2. $\mathcal{R}_2 = V \times X$. The interpretation of a rule $(w, x) \in \mathcal{R}_2$ is that the word $w \in V$ can be given type $x \in X$. These correspond to the dictionary entries in a categorial grammar.
3. $\mathcal{R}_3 = X \times \{ s \}$. The interpretation of a rule $r = (x, s) \in \mathcal{R}_3$ is that a word of type $x \in X$ can be the head of a grammatical sentence.

The language $L(G) \subseteq V^\star$ of a dependency grammar $G$ is defined as follows. A string $w_1 \dots w_n \in V^\star$ is grammatical if there are types $x_1 \dots x_n$, a binary relation $d \subseteq [n] \times [n]$ for $[n] = {1, \dots, n}$ with reflexive transitive closure $d^\star$ such that:

• $(w_i, x_i) \in R$ for all $i \leq n$, i.e. words are appropriately typed,
• $(i, i) \notin d^\star$, i.e. $d$ does not contain cycles,
• for all $i \leq n$, there is at most one $j \leq n$ with $(i, j) \in d$, i.e. every word depends on at most one head,
• if $i \leq j \leq k$ and $(i, k) \in d^\star$ ($(k, i) \in d^\star$) then $(j, k) \in d^\star$ ($(k, j) \in d^\star$), i.e. the dependency is a planar graph,
• $d$ is connected, or equivalently, there is exactly one head $h \leq n$ which doesn’t depend on anything, furthermore we have $(x_h, s) \in R$,
• for every $i \leq n$, we have $(u, x_i, v) \in R$ for $u = (x_j \vert j \leq i, (j, i) \in d)$ and $v = (x_j \vert j \geq i, (j, i) \in d)$ its left and right dependencies.

Drawing conventions

The conventions on how to depict such a dependency relation vary:

As string diagrams

We can reformulate the original definition in terms of the free rigid monoidal category generated by the symbols $V + X$ as objects and the rules $R$ as arrows. Then the convention (e.) where dependencies are represented as arcs is precisely a string diagram with the terminal symbols as domain and the start symbol $s$ as codomain.

Expressive power

Dependency grammars have equivalent expressive power to that of context free grammar and pregroup grammar.

We can translate a dependency rule $r = (u, x, v) \in R$ into a set of production rules $\{x \to u w v \vert (w, x) \in R\}$ for a context free grammar. Dependency grammars are precisely the context-free grammars with exactly one terminal symbol in the right hand-side of each production rule.

We can also translate a dependency rule $r = (u, x, v) \in R$ into a set of dictionary entries $\{w \to u^r x v^l \vert (w, x) \in R\}$ for a pregroup grammar.

However going in the other direction, i.e. from pregroup or context free to dependency grammar, the equivalence is weak: it preserves the set of grammatical strings but not their grammatical structure.

References

• Hays, David. Grouping and dependency theories. RAND CORP (1960)
• Gaifman, Haim. Dependency systems and phrase-structure systems. Information and control 8.3 (1965)
• Kruijff, Geert-Jan M. Dependency grammar. Encyclopedia of Language and Linguistics, (2006)