When looking on the web, wikipedia for example, at the concept of constituent, it is associated with the concept of phrase structure, and rather quickly with context-free languages (as the paradigmatic example), or more generally Linear Context Free Rewriting System (LFRS), which have standard, well analyzed formal definitions.

When looking at the concept of dependency, things seem to fall more on the linguistic theory side, with much less mathematical formalization. My question is whether there are accepted reference versions of dependency grammars that are well defined and analyzed from a mathematical point of view. Is there a specific dependency formalism that could play for dependency the paradigmatic role played by CF grammars for constituency?

When looking for example at the Wikipedia page for Dependency Grammars, there is no such formalisation that is suggested.

  • 2
    Most linguists don't pay any attention to the mathematical formalization. We think it's nice for the theoreticians to play with, but the formalizations don't represent any real autonomous systems, so they're basically irrelevant for real language description.
    – jlawler
    Aug 28, 2014 at 14:25
  • @jlawler, I agree with the sentiment in your comment. My exposure to heavy mathematical formalizations has not increased my understanding of the phenomena of syntax. Quite to contrary, it usually makes me feel bad because I don't understand. Aug 31, 2014 at 7:32
  • 3
    @jlawler I am a bit shocked by your comment and Tim Osborne's, in a way that is dual to other shocking answers I read on the physics site. Mathematical formalization does not make a linguistic theory, nor a physical one. But it is useful scaffolding to organize thoughts and understanding, maintain consistency and uncover inconsistencies (and for quantitative issues). It may be a game for theoreticians, but that is irrelevant, and sometimes their games can provide insight. I feel that physicist confuse too often equations and understanding. Could it be that linguists have the opposite failing?
    – babou
    Aug 31, 2014 at 14:33
  • Mathematics is only useful when applied to mathematical phenomenon, and it is far from clear that language is one of those. This is one reason why I'm attracted to ideas like the Natural Semantic Metalanguage, because rather than using an opaque and abstract symbols it uses ones based on language itself.
    – curiousdannii
    Sep 2, 2014 at 12:20

3 Answers 3


Some remarks are necessary before answering such a question. CFGs have been an important step in the history of formal grammars, but it is not exactly the example we want to follow in DG and in natural language modelling in general. CFGs are string rewriting systems, that is, grammars that generate sets of strings of words. But to speak English is not to be able to generate all the acceptable strings of words in English. To speak English is to be able to understand English sentences, that is, to associate a meaning to appropriate strings of words. Or conversely, to express every meaning we want to express, that is to associate a string of words to a meaning (excluding phonology, prodosy and so on). (This point was already stated by Tesnière 1959, ch. 6, §4: "speaking a language involves transforming structural order to linear order, and conversely, understanding a language involves transforming linear order to structural order.") CFGs have been successful because the derivation of a string can be interpreted as a constituency tree. But the CFG itself does not really generates the constituency tree. This problem was solved with the tree grammars, and the most famous of them, TAG (Joshi et al. 1975). Such grammars are interesting because they simultaneously generate a string of words and a tree structure. This is a good step in the direction we want to follow to model natural languages and define formal DGs.

Now we can answer the question. We can propose grammars generating strings whose derivations can be interpreted as dependency trees. It is even possible with CFGs (see the strong equivalence between Hays' grammars and "lexicalized" CFGs in gaifman 1965). But it is not really what we want. It is simpler and more useful to define grammars that directly generates linearly ordered dependency trees (which is more or less equivalent to transductive grammars associating strings (= linear order) to dependency trees). A very simple way to generate a linearly ordered dependency tree is to generate it by pieces, like TAG with constituency trees. The simplest DG we can imagine as only to kind of rules:

  • lexical rule generating nodes, for instance (Mary, N), (Peter, N), (loves, V) …

  • dependency rules generating dependecies, for instance (V, N, subj, <), (V, N, obj, >) …

The rule (Mary, N) says that "Mary" is a noun (N). The rule (V, N, subj, <) says that between a V and N we can generate a subject dependency where the dependent (N) is before (<) the governor.

Such a grammar generates "Mary loves Peter" and its dependency tree.

For the details and the generative as well as the transductive interpretation of such a grammar, see my paper: KAHANE Sylvain, 2001, What is a natural language and how to describe it? Meaning-Text approaches in contrast with generative approaches, Invited talk, Computational Linguistics, Proc. CICLing, Mexico, Springer Verlag, 1-17.

The previous grammar is very simple. It only works if we suppose that the dependency tree is projective. To generate non projective depednency trees we need a more complicated formalism, such as topological grammars (GERDES Kim & KAHANE Sylvain, 2001, Word order in German: A formal dependency grammar using a topological hierarchy, ACL, Toulouse) The previous grammar cannot control the subcategorization. To do that we can extend the locality domain of the rules and to have rules corresponding to bigger pieces of the tree than just one node or one dependency (Kahane S. (2006) Polarized Unification Grammars, Coling-ACL, Sydney). Note that this last formalism, PUG, is a "paradigmatic" formalism which allows to define a wide paradigm of grammars.

  • Your distinction between CFG and TAG is surprising. I see them as two variants of a single paradigm. Automata theory often considers grammars as pure string generating devices, but they do impart structure on the strings. It is explicit for TAG, with the separation of derivation and derived tree. CFG uses simple constituents so that these two trees are isomorphic. To put it differently, CFG are just Regular Tree Grammars. Being on the low end, they offer less descriptive power, in the same way that while CFG do impart some generative structure on strings, Regular Grammars do not.
    – babou
    Sep 1, 2014 at 21:31
  • I understand some of the answer. For instance, I understand how the combinatory rules of the mini-grammar are supposed to work. Other parts of the answer are difficult for me to get, despite the fact that I am well-versed in DG. My overall sentiment remains intact. How do these formalisms help us understand concrete phenomena of syntax better? How do these formalisms shed light on ellipsis, for instance. Discussions that focus on formalization rarely go beyond really simple data, e.g. "Fred likes Susan." Sep 2, 2014 at 3:55
  • @babou: yes you can see CFG has a particular case of tree-rewriting system. It is like that we like to see it now. My point was just that DGs must be define as tree-rewriting system. Sep 2, 2014 at 8:48
  • @Tim: A formalism just help you to formalize your modeling. When your modeling is formalized, you can make computations and predictions and your modeling can be falsified. But the formalism does not help you to make theoretical choices. You can write an isolated paper on ellipsis, but if you want to now how your modeling interact with other phenomena, you must have a formalism that acknowledge all of them. Your last remark is strange: We now have a lot wide coverage grammar in a lot of formalisms. Very complex phenomena like wh-extraction have been the cornerstone of formalization since 70s. Sep 2, 2014 at 9:04

The formalizations of dependency theory exist. In fact I have a colleague who specializes in mathematical formalizations of principles of syntax, and he is more a DG guy (dependency grammar) than a PSG guy (phrase structure grammar). But he and I disagree about the value of the formalizations that he employs. I do not understand his formalizations and see little value in them, and he probably thinks I am of inferior intellect because I do not understand his formalisms.

The question uses a couple of terms that I am not sure about. For instance, what exactly is meant by "paradigmatic formalism"? If what is meant is the context free rewrite rules of early Chomskyan syntax, they can easily be reworked in terms of dependency. See the question and my answer here in this regard.

Concerning the constituent unit, the question is correct that it is associated more with constituency grammars (= phrase structure grammars) than with dependency grammars. However, if one defines the constituent over tree structures as done in many syntax textbooks (of phrase structure grammars), then the constituent unit is valid for both dependency-based and constituency-based structures. On both approaches, a constituent is a complete subtree. The main difference in this regard is that dependency-based structures acknowledge many fewer constituents than phrase structure grammars. This point is discussed and debated at length here (in an entertaining and heated fashion).

A few basic facts about the status of dependency grammar can be helpful at this juncture. Dependency-based theories of syntax have been on the periphery of the mainstream for about 50 years. The dominance of constituency (as associated with the Chomskyan tradition) is undeniable. However, in the past 15 years or so, dependency is gaining ground, especially among computational linguists. Dependency-based structures are really simple and transparent compared to constituency-based structures, hence they seem to be more appropriate for the goals pursued by computational linguists, who are less motivated by the theoretical stringency of the syntactic models they assume. My personal view is that the simplicity and transparency of dependency structures also translates to a more solid and emperically verifiable theory of natural language syntax in general, and I enjoy debating the point with anyone who wants to have a go at it.

So in sum, the impression expressed in the question that dependency seems to be less formalized from a mathematical point of view is not something that DG people like me worry about. In fact I'm comfortable with this state of affairs, since I view many of the formalizations as a diversion, a sort of smoke screen. In fact my suspicion is that heavy mathematical formalizations applied to syntactic structures is a way a masking the fact that one does not really have anything insightful to say about the linguistic phenomena one claims to be investigating.

  • I read your answer when I wrote my question. It is indeed pretty close to constituency. I guess that Head Grammars, which are constituency based, aim however at formalizing dependency. I am only wondering whether there are formal structures that would emphasize abstractedly the key aspects of dependency, as opposed to constituency, or more closely to lexicalization, which is itself a rather old issue which you emphasize, with some excess imho, in your quoted answer. (see also my other comment to John Lawler).
    – babou
    Aug 31, 2014 at 15:26
  • It may be that mathematical formalizations just hide the lack of insightful vision. Maybe, that also means that formalization does away with what is understood and no longer requires insight, so that the scientist can better focus on what needs more insight and is not yet covered by formalization. Now, you might answer me that dependency is pure linguistics theory that is perfectly expressible through the consistuency formalization, through the way the grammar is constructed. That would be an answer, somehow breaking a kind of implicit symmetry that seem to oppose constituency and dependency.
    – babou
    Aug 31, 2014 at 15:27
  • @babou, I think my colleague and you are of the same mind. He has a strong background in theoretical mathematics. I have pointed him to our exchange here, but so far, he is silent. I think he is in a position to demonstrate that dependency-based models can be just as mathematically rigorous as constituency-based models. For my part, I would enjoy seeing how he answers your question. Aug 31, 2014 at 21:18
  • You do not really answer my question, which I believe is rather precise. Still, I think it is a kind of indirect answer, by refusing to address the question as stated. I was only asking (with no hidden agenda or quality judgement) whether dependency had formalizations with the same status as some constituency formalizations. My feeling is that there are such formalizations, but they do not have the same recognition and formal development as the constituency ones. It may be due to the fact that they differ more in linguistic perspicuity than in formal generative power.
    – babou
    Sep 1, 2014 at 22:04
  • I find that the answer you link to about reworking the CFG rewrite rules for dependency grammar provides much of the answer, or avoids a key aspect of the question, at least in my flavor of the question. As to the "philosophical" writings of Tesnière about dependency being more appropriate, I never saw much insight from that direction, it seems rather arbitrary to look at language that way, unless there are sounder writings as @babou seemed to be looking for too.
    – matanox
    Nov 23, 2017 at 19:30

What you're seeing is more of an illusion of history. Both constituency and dependency analysis have their origins in theories of syntax. It is an accident of history that the most famous algorithmic formalisation of syntactic analysis is based on constituent analysis.

Both produce trees and can therefore be subjected to tree analysis and graph theory. Both dependency and constituent-based grammars can be generative and non-generative and therefore will be concerned with different aspects of the formalism.

  • At first sight, I have no problem with what you are saying, in the sense that historical accidents, or presumed such, are orthogonal to my concern. But if what you state is actually the case, there should be standard formalizations of dependency. My question is precisely: what are these formalizations? Is there one that exhibits the more fundamental characteristics of dependency in the way CFG do it for constituency, even though there is more than CFG to constituency?
    – babou
    Aug 31, 2014 at 10:36
  • 1
    Constituency stems in a large part from the binary division of the clause into subject and predicate. Traditional grammar took that division from term logic. I'm not sure one can characterize term logic as an "accident of history". Perhaps it is accidental, however, that the linguists who have influenced our thinking about syntax the most in the last century (Bloomfield, Chomsky, etc.) were never challenged early in their development as linguists to motivate the division linguistically. Aug 31, 2014 at 11:20
  • For an early formalization of dependency structures along the lines of the context free rewrite rules associated with early Chomskyan syntax, see this seminal article: Hays, David G. 1964. Dependency theory: A formalism and some observations. Language 40, 511-525. Hays presents context free rewrite rules for dependency structures. Perhaps this is what the question is looking for. Aug 31, 2014 at 11:30
  • @babou It has been a long time, but I remember sitting through interminable classes on mathematical linguistics looking at graph theory and dependency trees. So, yes, there are formalisms (at least when it comes to the generative strands of dependency syntax) but I'd have to track down my notes to say more. It is important to know that the constiuency approach itself did not produce the sort of formalization you're looking for until long after it was first introduced. And your typical constituent analysis found in many papers will be quite informal. Sep 4, 2014 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.