How can one best formalize dependency structures in terms of rules?

Question

I am looking for guidance in forming mathematically-inspired rules for dependency syntax. I know about the rewrite rules for dependency structures produced by Hays (1964), but I am wondering whether that is the best way to formalize dependency structures. For my particular research goals, I actually do not need the formal rules, and in fact I think heavy use of formalisms renders linguistic investigations opaque. I am, however, being confronted with critique that to have a plausible theory of syntax, one needs to develop the formal side. Hence my interest and question.

Answer 1

If one wants to show that a theory of syntax is plausible, it's necessary to implement it in such a way that well-formed sentences are accepted (and assigned a sensible syntactic structure) and ill-formed sentences are rejected. To this end one needs either rules or a mechanism for building up syntactic structures from lexical items (as in categorial grammars). In fact, one often uses a mix of both.

In the examples below I'll use a system used to teach the basics of theoretical syntax to undergraduate students in Edinburgh, Saarbrücken and Prague (and probably elsewhere), which is based on Alain Colmerauer's Q-systems (Alain Colmerauer (1969): "Les systèmes Q ou un formalisme pour analyser et synthétiser des phrases sur ordinateur"). The examples can be tested out on a computer using this interpreter.

Before writing down the rules one needs a lexicon. Producing one is rather boring and for the purposes of a toy grammar it's customary to define a few lexical items so the rules can be tested out.

Dependency grammars often use positional pattern rules and the order in which they're applied gives rise to a tree where the roots of subtrees are categorial heads. Such a tree is always projective and contains all the words in the sentence. One also needs an ancillary data structure to control the process of analysis (e.g., to rule out a tree when there's no obligatory agreement). This structure is often based on unification and can also contain lexico-semantic data (argument structure, conceptual structure) which effect the syntax-semantics interface (after all, syntax is just an interface between the linear form of a sentence and its meaning). When it combines morphological and lexico-semantic data, it's sometimes called morpholexical structure, reflecting its ragbag nature.

The tool linked to above interprets rewriting systems with rules of the form

Det + N == NP.

This is superficially similar to phrase structure grammars but since it's a rewriting systems, it rewrites the input string so no phrase structure tree is produced. In actual fact, such rules produce something like dependency trees but with categorial heads as roots of subtrees (most dependency grammars use functional heads). Virtually all rules use arguments so a more useful rule would look as follows:

Det(T(the,@)) + N(T(duck,@)) == NP(T(duck,T(the,@),@)).

The T-argument represents the corresponding tree. The first subargument is the label of the root node and @ marks the position of the root in the subtree. For example, T(duck,T(the,@),@) is a small tree whose root is duck and whose only child is the, which appears to the left of its (categorial) head. Note that if you accepted the DP-hypothesis, the determiner would be the head. The iterative application of rules builds up the tree and the argument/conceptual structure in step.

Here's the code of the example:

W(the, $i) == Det(T(the,@)) [* def=1] .
W(duck, $i) == N(T(duck,@)) [* str func=duck & * str index=$i].

-DIV-

N($X) [*=%] == N'($X) .
N'($X) [*=%] == NP($X) .
Det($X) [*=%] + N'(T($Y,$U...)) [*=%] == NP(T($Y,$X,$U...)) .

The first part is what would be the lexicon. The second part is a formalisation of the rules analysing the simple noun phrase. The expressions in square brackets are annotations that define the argument/conceptual structure via unification and can be ignored in first experiments (the grammar will slightly overgenerate without them). If the rules are placed in a file named test.gr, then the rule set can be tested out using the following command:

qsys -i "the duck" test.gr

Of course this is all very simple, at my university undergraduate student of theoretical syntax learn this (and much more) in their first year, but it's the first step in formalising a prospective theory.

The answer is now quite long, questions/suggestions welcome on what to explain in more detail.

(The used software is in the public domain to the best of my knowledge.)