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 .