3

Theoretically speaking, if I were to use a rule-based approach to generate grammatically correct strings for a language L, I would implement a phrase structure grammar G = (V, T, R, S) consisting of non-terminals, terminals, and rewrite rules. This approach would be constituency based and rely on recursion.

Is there an equivalent way to use dependency grammar to generate the same strings? How would one formally describe such a system? (A brief stint on Google yielded this prolegonema and a handful of other articles, but otherwise the subject matter on this seems to be sparse.)

hippietrail
  • 14,687
  • 7
  • 61
  • 146
player.mdl
  • 507
  • 4
  • 14

1 Answers1

3

The context free rewrite rules - as associated most with early Chomskyan syntax - can easily be reworked in terms of dependency: G = (T, R), where T is the set of terminals and R is the set of rewrite rules. The distinction between nonterminal symbols (V) and terminal symbols (T) disappears, only terminals remaining. If one needs a start symbol, it would probably be V (verb). Standard context free rewrite rules (i.e. constituency-based rewrite rules) have the folllowing form:

 VP --> V NP

 NP --> AP N

 AP --> Adv A

These same rules in the dependency-based system might be expressed as follows:

 V --> __ N

 N --> A __

 A --> Adv __

The "__" marks the position of the head. The first rule states that a verb takes a noun as a postdependent; the second rule states that a noun takes an adjective as a predependent; and the third rule states that an adjective takes an adverb as a predependent. These rules could generate the string: drink very cold beer. It should be apparent that the same sort of recursion associated with the constituency-based rewrite rules is also possible with dependency-based rewrite rules of this sort, e.g. V --> __ V.

According to Frazier (the paper you linked to), Gaifman (1965) produced such dependency-based rewrite rules, and if I remember correctly, Hays (1964) does something similar. Hays' paper is in the literature list of Frazier's paper (again, the paper you linked to).

I think some more general comments about rewrite rules are warranted. Theoretical syntax mostly abandoned rewrite rules decades ago. The number of rewrite rules that one needs to begin to accommodate the combinatory potential of the lexical items of natural language is very large (certainly at least in the hundreds), so large that the notion of rewrite rules existing separate from the lexical items is not really insightful. Rewrite rules seem to remain prominent in computational circles, but most of theoretical syntax now views them with skepticism, their value residing mainly in the role they have played in the development of syntactic theory.

Consider that standard constituency-based rewrite rules generate structure top down. In contrast, the MP (Minimalist Program, Chomskyan syntax since about 1995), generates structure bottom up. Thus if one wanted to employ rewrite rules for modern Chomskyan syntax, one would have to invert and reverse the vertical and horizontal order of the rules, e.g. 

 Adv A --> AP

 AP N --> NP

 V NP --> VP

These rules would generate the string drink very cold beer working from the bottom of the structure moving upwards.

Much of modern syntactic theory (in theoretical circles) is now more lexicalist than early Chomskyan syntax. What this means in part is that syntax is understood more in terms of the combinatory potential of lexical items (think subcategorization and valency) than in terms of combinatory rules that exist independently of the lexical items.

Tim Osborne
  • 5,747
  • 1
  • 17
  • 40
  • How would one account for word order? Take the SOV word order found in subordinate clauses in Dutch or Afrikaans, for example. Knowledge of what is dependent on what doesn't encode how to order words differently than in the SVO order of main clauses. In phrase structure grammars, word order is implicit. That does not seem to be the case for DGs. – player.mdl Apr 06 '14 at 09:39
  • The challenge of addressing word order in SOV clauses is similar for both grammars, dependency- or constituency-based. Both grammar types have to augment the theoretical apparatus in one way or another to address the variable word order associated with scrambling: https://en.wikipedia.org/wiki/Scrambling_%28syntax%29. An article demonstrating how this is done in DG with numerous trees of German examples is here: http://www.linguistics.fi/julkaisut/SKY2009/Gross_Osborne_NETTI.pdf. – Tim Osborne Apr 06 '14 at 16:14
  • What will happen when a constituent governs more than one dependent? In the example above, let's say we add a determiner. Both the determiner and the AP would then be dependent on the noun. Even if this is defined with the governor explicitly on the right hand side of each dependent (N --> D __ and N --> AP __ ), what's to stop the grammar from generating, say, "very cold the beers" instead of "the very cold beers"?

    In a CG, the word order will already be encoded, on account of the fact that more than one terminals / non-terminals are allowed on the right hand side of the rewrite rule.

     – player.mdl Apr 07 '14 at 19:47
  • @player.mdl, the issue is the same for constituency-based rewrite rules, e.g. "send her to Europe". Early constituency-based rewrite rules assumed flat VPs, hence one would have VP --> V N PP for this example. Dependency can do the same thing, e.g. V --> __ N P. For the example "the very cold beer", the dependency-based rewrite rule would be: N --> D A __. Note that the issue you point to kills the dependency-based approach outright if only binary-branching structures are allowed, since the depedency-based approach cannot be limited to strict binarity of branching. – Tim Osborne Apr 07 '14 at 20:14
  • @player.mdl, thus the issue surrounding strict binarity of branching is crucial for DG in general. If one could convincingly demonstrate that all branching is binary, that would be an existential challenge for DG. If you are interested, I have empirical considerations ready to go demonstrating that a flat analysis "the very cold beer" is plausible. – Tim Osborne Apr 07 '14 at 20:20
  • I am actually quite interested. All the literature I read thus far stressed the binary principle. – player.mdl Apr 07 '14 at 20:32
  • @player.mdl, from a theory-neutral, emperical standpoint, the layered analysis of an NP such as "this very cheap wine" has been motivated in two ways, in terms of coordination and in terms of the indefinite pronoun "one". Concerning coordination, one argues that "very cheap wine" must be a constituent because it can be coordinated, e.g. "this [very cheap wine] and [quite expensive beer]". By this same reasoning, however, one would have to view the "this very cheap" as a constituent, e.g. "[this very cheap] and [that quite expensive] wine". – Tim Osborne Apr 07 '14 at 21:02
  • @player.mdl, further such examples where the coordinated strings cannot be construed as constituents, given strict binarity of branching or otherwise: "[these good] and [those bad] ideas", "[the old] and [the new] submarines", "[before a meager] and [after a meager] meal", etc. If you look to Afrikaans, my guess is that such examples are just as plausible in Afrikaans. In the big picture, such data undermine claims that all branching is strictly binary within NPs. – Tim Osborne Apr 07 '14 at 21:07
  • @player.mdl, concerning the "one" test, the following data have been used to motivate the layered analysis of NPs: "this good explanation of gapping and that bad one". It appears as though "one" is standing in or "explanation of gapping", which is construed as evidence that "explanation of gapping" is a constituent. This reasoning crashes, however, when the following example is added: "this good explanation of gapping and that one of stripping". It now appears as though "one" is standing in for "good explanation". – Tim Osborne Apr 07 '14 at 21:14
  • @player.mdl, Well, there is no way to simultaneously view both "explanation of gapping" and "good explanation" as constituents in a single tree. Such a tree cannot be produced. Try it. The point then, is that counterexamples can be produced that undermine the standard means for motivating the layered structures involving strict binarity of branching in NPs (and otherwise). Given such contradictory data, the flat analysis of NPs and other structures seems quite plausible. – Tim Osborne Apr 07 '14 at 21:22
  • @player.mdl, If you'd like to see these issues and others developed in detail, send me an email. I will hook you up with the relevant literature. My email address is on my Wikipedia page here: https://en.wikipedia.org/wiki/User:Tjo3ya. – Tim Osborne Apr 07 '14 at 21:27
  • Are you saying that the transformation you propose at the beginning of your answer can be applied in a systematic way to any CF grammar, so that any CF language will have such a dependency grammar. And is there an inverse transformation? (cf your other answer) – babou Jun 21 '15 at 22:18
  • Yes, I guess. Hays (1964) is the paper to read in this regard. That paper was foundational for dependency-based syntax. He develops rewrite rules like the ones I give above. He explores the extent to which they are weakly or strongly equivalent to the standard constituency-based rewrite rules. I am not sure what you mean by "inverse transformation". – Tim Osborne Jun 25 '15 at 00:41