dependency grammar

Dependency grammars are a kind of formal grammars based on the notion of dependency graph, rather than constituency trees.

The original definition is from Gaifman (1965).

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 \in R$ which have one of the following shapes:

- $r = (y_1 \dots y_k)^r x (y_{k + 1} \dots y_{k'})^l \to x$ for $x \in X$, $k' \geq k \geq 0$ and $y_1, \dots, y_{k'} \in X$. $(-)^l$ and $(-)^r$ denote the left and right adjoint as in a pregroup grammar. The intended meaning is that words of type $y_1, \dots, y_n$ can depend on a head of type $x$ when they appear in this order.
- $r = w \to x$ for $w \in V$ and $x \in X$. These correspond to the dictionary entries in a categorial grammar.
- $r = x \to s$ for $x \in X$ and $s$ the start symbol.

The language $L(G) \subseteq V^\star$ of a dependency grammar $G$ is traditionally 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 \to 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 \to s \in R$,
- if $i \leq n$ depends on $j_1, \dots, j_k$ on its right and $j_{k + 1}, \dots, j_{m}$ on its left, then we have $(y_l \dots y_k)^r x_i (y_{k + 1} \dots y_{k'})^l \to x_i \in R$.

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

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.

The original definition has equivalent expressive power to that of context free grammar and pregroup grammar. Note that these equivalences are *weak* however: they do not preserve the structure of the diagrams. It has been extended to a mildly context-sensitive grammar by allowing the dependency graph to be non-planar, i.e. braidings are allowed in the grammatical derivation.

- 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)

Last revised on December 1, 2020 at 08:44:01. See the history of this page for a list of all contributions to it.