Definition of dependency structures

A dependency structure over sentence S = w₁ w₂ ... w_n is an ordered pair <N,f,R> where:

• N is a finite, non-empty set of nodes
• f is a function from N to {i | W_i ∈ S}, i.e. every node is labelled with exactly one token from the sentence (but nothing stops the same token labelling more than one node)
• R is an irreflexive, rooted relation on N, i.e. no self-arcs, and there is exactly one element of N which is a source but not a target

Optional constraints

An 'acyclic' dependency structure over sentence S is a dependency structure <N,f,R> over S where:

• if there is a sequence of R-arcs from node n₁ to node n₂, then there is no sequence of R-arcs from n₂ to n₁

A dependency 'tree' over sentence S is an acyclic dependency structure <N,f,R> over S where:

• every node is a target of at most one arc, i.e. no re-entrancy

A 'surjective' dependency structure over sentence S is a dependency structure <N,f,R> over S where:

• f is a surjective function, i.e. every token in S labels at LEAST one node in N

An 'injective' dependency structure over sentence S is a dependency structure <N,f,R> over S where:

• f is an injective function, i.e. every token in S labels at MOST one node in N

A 'bijective' dependency structure over sentence S is a surjective, injective dependency structure <N,f,R> over S, i.e. every token in S labels EXACTLY one node in N

Most dependency parsers assume bijective dependency trees. Recent work (based on Danish Dependency Treebank) has relaxed the tree constraint i.e. bijective acyclic trees. There are good reasons for relaxing the surjective constraint (expletive pronouns) and the injective constraint (argument cluster coordination, noun modifier coordination).

Projectivity

A 'projective' dependency tree over sentence S = w₁ w₂ ... w_n is a dependency tree <N,f,R> over S, where: *

Others

Functionality - for each word W and each dependency label T, there is no more than one dependency from W labelled with T

-- MarkMcConville - 14 Aug 2008