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.