nLab
dependency grammar

Contents

Contents

 Idea

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

Original Definition

The original definition is from Gaifman (1965).

A dependency grammar is a tuple G=(V,X,R,s)G = (V, X, R, s) where VV and XX are finite sets of terminal and non-terminal symbols with the start symbol sXs \in X and a finite set of rules rRr \in R which have one of the following shapes:

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

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

  • (w ix i)R(w_i \to x_i) \in R for all ini \leq n, i.e. words are appropriately typed,
  • (i,i)d (i, i) \notin d^\star, i.e. dd does not contain cycles,
  • for all ini \leq n, there is at most one jnj \leq n with (i,j)d(i, j) \in d, i.e. every word depends on at most one head,
  • if ijki \leq j \leq k and (i,k)d (i, k) \in d^\star ((k,i)d (k, i) \in d^\star) then (j,k)d (j, k) \in d^\star ((k,j)d (k, j) \in d^\star), i.e. the dependency is a planar graph,
  • dd is connected, or equivalently, there is exactly one head hnh \leq n which doesn’t depend on anything, furthermore we have x hsRx_h \to s \in R,
  • if ini \leq n depends on j 1,,j kj_1, \dots, j_k on its right and j k+1,,j mj_{k + 1}, \dots, j_{m} on its left, then we have (y ly k) rx i(y k+1y k) lx iR(y_l \dots y_k)^r x_i (y_{k + 1} \dots y_{k'})^l \to x_i \in R.

Drawing conventions

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

conventions vary

As string diagrams

We can reformulate the original definition in terms of the free rigid monoidal category generated by the symbols V+XV + X as objects and the rules RR 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 ss as codomain.

Expressive power & extensions

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.

References

  • 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.