Organizations: Universidade da Coru˜na, CITIC, Departamento de Ciencias de la Computación y Tecnologías de la Información, Campus de Elvi˜na, s/n, 15071 A Coruña, Spain · Universitat Politècnica de Catalunya, Departament de Ciències de la Computació, Campus Nord, 1–3, 08034 Barcelona, Spain
Dependency syntax represents the structure of a sentence as a tree composed of dependencies, i.e., directed relations between lexical units. While in its more general form any such tree is allowed, in practice many are not plausible or are very infrequent in attested language. This has motivated a search for constraints characterizing subsets of trees that better fit real linguistic phenomena, providing a more accurate linguistic description, faster parsing or insights on language evolution and human processing. Projectivity is the most well-studied such constraint, but it has been shown to be too restrictive to represent some linguistic phenomena, especially in flexible-word-order languages. Thus, a variety of constraints have been proposed to seek a realistic middle ground between the limitations of projectivity and the excessive leniency of unrestricted dependency structures.
Figures & tables
Figure 1: A dependency tree in Universal Dependencies format for an Irish sentence (“A large bed dressed in a yellow silk blanket”). The root is shown in boldface.
Figure 2: Projectivity and 1-planarity. For each tree, the root is shown in boldface, and we show the projection of the word highlighted in italics. The top tree is projective and planar (the continuous projection of account is highlighted). The tree in the middle is planar, but not projective (the projection of перевiрити is discontinuous). The bottom tree is neither projective nor planar (it has a discontinuous projection and arc crossings, marked with red circles). The second sentence is taken from a Ukrainian UD treebank (version 2.6); it can be translated as “”You might want to check out what it’s like around … 2023,” O’Reilly joked”. The third sentence is taken from a Czech parallel UD (PUD) treebank (version 2.6); it can be translated as “The Dutch students have yet to decide if they will be commercializing their electric motorcycle”.
Figure 3: Well-nestedness and gap degree. The top tree is well-nested and has gap degree 0 (two example projections, which are continuous and do not interleave, are shown in red and blue). The middle tree has gap degree 1 (as the projection of a has a gap) but it is still well-nested. The bottom tree has gap degree 1 and is ill-nested, as the projections of a and b interleave.
Figure 4: The WGk sets. The top tree is in WG0 , the middle tree is not in WG0 but it is in WG1 (a projection with gap degree 1, but which does not interleave any other projection, is highlighted), and the bottom tree is not in WG0 or WG1 but it is in WG2 (a projection with gap degree 2, but which does not interleave any other projection, is highlighted).
Figure 5: Multiplanarity. The 1-planar tree has no dependency crossings. In the 2-planar tree, we can split the arcs into two planes (associated here with colors) such that arcs within the same plane do not cross. The last tree is not 2-planar, so it is not possible to do this with two colors, but it is 3-planar, since it is possible with three colors, as shown. Note that the three dependency trees are linear arrangements of the tree shown above: they have the same structure, but the order of the words (represented by numbers) changes. Indeed, projectivity, planarity, and all the other properties discussed here can be seen as properties of word order. In fact, every dependency tree can be reordered into a projective tree, and some parsing strategies have exploited this ( Nivre, 2009 ) .
Figure 6: A “book embedding” 3D view of the bottom tree in Fig. 5 . The tree is 3-planar because its arcs can be drawn on three pages of a book, such that arcs within the same page do not cross.
Figure 7: Two views of the same 1-Endpoint-Crossing tree. The left view highlights the arcs crossing one given arc (dotted), showing that they have the node w2 in common. The right view focuses on a different arc (dotted), such that all its crossing arcs have w9 in common. Colors represent planes, showing that the tree is also 2-planar, like all 1-Endpoint-Crossing trees.
Figure 8: The MHk sets. The left tree is in MH4 (and is also 1-Endpoint-Crossing, but it is not well-nested). The right tree is not in MH4 , but it is in MH5 (and well-nested, but not 1-Endpoint-Crossing). Note that while well-nestedness and the 1-Endpoint-Crossing property can be easily inferred from the graphical representation, it is not know how to do this for the operationally-defined MHk sets.
Figure 9: An inclusion diagram with the known inclusions between the major classes of dependency trees that we have discussed. A path from set A to B in the graph means that A⊆B .
Despite their widespread use, the principles governing the organisation of syntactic dependency trees remain poorly understood. I analyse dependency trees from 124 typologically, genetically, and geographically diverse languages. Their topology departs systematically from randomness. Relative to uniformly sampled random trees, dependency trees exhibit greater structural robustness and lower branching heterogeneity. I propose that these universal regularities emerge naturally from incremental grammatical encoding. I model this process using sublinear preferential attachment. The model accurately reproduces the observed topology. More generally, the results demonstrate how a universal statistical property of syntax can emerge from a simple, cognitively motivated generative process. They further illustrate a broader principle of efficiency by construction: communicatively efficient syntactic structures can emerge without direct optimisation for communication.
Fermín Moscoso del Prado Martín
Department of Language and Communication & Center for Language Studies Radboud University Erasmuslaan 1, 6525 NL, Nijmegen, The Netherlands
Dependency length minimization (DLM) is a well-documented processing universal, but previous studies report a single mean dependency distance (MDD) per language, obscuring variation across syntactic relation types. We analyze 122 languages in UD and SUD (version 2.17), showing that DLM operates on two distinct levels. Grammar-driven optimization targets functional dependencies (det, case, aux), which are universally short (mean 1.71, σ = 0.33) and invariant across typologically diverse languages. Processing-driven optimization operates on lexical dependencies (nsubj, obj, obl), which are longer (mean 2.87), highly variable (σ = 0.63), and constrained by word-order typology. This asymmetry holds in SUD despite reversed head direction (r = 0.92). We conclude that ''the grammar does the work'' of minimization by scaffolding sentences with local functional attachments, leaving processing pressures to determine the ordering of lexical heads.
Kim Gerdes
LISN, Qatent, STL · Université Paris-Saclay, LISN (CNRS) Orsay, France
Arc-standard derivations over projective dependency trees can be interpreted as the incremental construction of lexicalized ordered trees with contiguous yields. Each shift, leftarc, and rightarc transition corresponds to a deterministic tree update, and the resulting ordered tree uniquely determines the dependency arcs introduced by the derivation. We show that this representation is not an arbitrary encoding: a single-headed dependency tree admits such a contiguous ordered representation if and only if it is projective. The proposal is therefore derivational rather than conversion-based, since the ordered object is defined over the transition sequence itself rather than obtained by transforming a completed dependency graph. This gives a tree-theoretic interpretation of arc-standard parsing, in which projective dependency derivations implicitly construct recoverable constituency-style ordered trees. For non-projective inputs, the interpretation can be used through pseudo-projective lifting and inverse decoding. A small implementation study confirms that the mapped derivations are executable in an existing neural transition-based parser.