Formal Constraints on Dependency Syntax
Pith reviewed 2026-05-10 19:51 UTC · model grok-4.3
The pith
Formal constraints on dependency trees seek a middle ground between the restrictiveness of projectivity and the leniency of unrestricted structures.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper shows that while projectivity is too restrictive for some linguistic phenomena, fully unrestricted dependency trees are too permissive, motivating the definition and study of intermediate formal constraints that characterize subsets of trees better aligned with attested data.
What carries the argument
Formal constraints defining subsets of dependency trees that exclude implausible structures while permitting observed phenomena.
If this is right
- More accurate syntactic descriptions for languages with non-projective constructions.
- Parsing algorithms that run faster than unrestricted models yet cover attested cases.
- Quantitative measures for comparing how well different constraint sets match human language.
- Potential links between constraint choice and patterns of language change over time.
Where Pith is reading between the lines
- Such constraints could be combined with statistical models to improve accuracy in dependency parsers for low-resource languages.
- They might reveal universal tendencies in human syntax that cut across individual languages.
- Extensions could test whether the same constraint sets predict processing difficulty in psycholinguistic experiments.
Load-bearing premise
These constraints actually select trees that fit real language data better than either projectivity or no constraints at all.
What would settle it
A large-scale comparison on treebanks showing that the frequency or acceptability of trees allowed versus disallowed by the proposed constraints does not differ meaningfully from projectivity or unrestricted cases.
Figures
read the original abstract
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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript motivates the study of formal constraints on dependency syntax. It observes that dependency trees in their unrestricted form are too permissive while projective trees are too restrictive for certain attested phenomena (especially in flexible word-order languages), and therefore surveys or formalizes a family of intermediate constraints intended to characterize linguistically plausible subsets of trees. These constraints are positioned as improving linguistic description, parsing efficiency, and theoretical understanding of language evolution and processing.
Significance. A rigorous formal treatment of such constraints would be valuable for computational linguistics, as it could yield more accurate parsers and falsifiable predictions about attested tree distributions. The paper's emphasis on formal characterization is a potential strength if it supplies precise definitions, closure properties, or comparative analyses that go beyond the well-known projectivity baseline.
minor comments (1)
- [Abstract] The abstract remains purely motivational and does not preview the specific constraints examined, any new formal results, or the evaluation methodology. Adding a sentence that names the main constraint families or states the central theorem/empirical finding would improve reader orientation.
Simulated Author's Rebuttal
We thank the referee for their positive summary of our work on formal constraints for dependency syntax and for recommending minor revision. The manuscript surveys and formalizes intermediate constraints between projectivity and unrestricted trees to better capture attested linguistic phenomena.
read point-by-point responses
-
Referee: No major comments were listed in the report (the MAJOR COMMENTS section is empty).
Authors: We note the absence of specific major comments. We will incorporate any minor revisions as recommended in the next version of the manuscript. revision: yes
Circularity Check
No significant circularity
full rationale
The paper's abstract and visible content are purely motivational and descriptive, noting the limitations of projectivity and the existence of proposed constraints as a middle ground without advancing any derivation, theorem, prediction, or quantitative claim. No equations, fitted parameters, self-citations as load-bearing premises, or first-principles results are present that could reduce to inputs by construction. The work surveys and motivates formal constraints on dependency trees but does not claim to derive any specific result from prior inputs within the paper itself, rendering circularity analysis inapplicable.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
A large bed dressed in a yellow silk blan- ket
Formal Constraints on Dependency Syntax Carlos G´omez-Rodr´ ıguez,a and Llu´ ıs Alemany-Puigb aUniversidade da Coru˜na, CITIC, Departamento de Ciencias de la Computaci´on y Tecnolog´ıas de la Informaci´on, Campus de Elvi˜na, s/n, 15071 A Coru˜na, Spain bUniversitat Polit`ecnica de Catalunya, Departament de Ci`encies de la Computaci´o, Campus Nord, 1–3, 08...
work page 2019
-
[2]
Formal Constraints on Dependency Syntax
Note that, as can be seen in the figure, dependency arcs are labelled with syntactic functions (like AMOD for an adjectival modifier). However, these labels do not affect the constraints defined in this chapter, so we will omit them from now on. 2We use the notation where dependencies go from head to dependent as it has become the de facto standard in the...
work page internal anchor Pith review Pith/arXiv arXiv 2026
-
[3]
or pointer-network parsers (Fern´andez-Gonz´alez & G ´omez-Rodr´ıguez, 2019), and sequence- labeling parsers (Strzyz et al., 2019)). In some definitions, an extra node that acts as a dummy root is added to the dependency tree, typically identified with index 0 and thus located to the left of the nodes representing actual words, although it can also be pla...
work page 2019
-
[4]
the mathematical code of syntax
or Japanese (Tanaka, 1997; Kurohashi & Nagao, 1997), have traditionally as- sumed that crossing dependencies do not exist. According to Ninio (2017), projectivity, “the mathematical code of syntax”, is “per- vasive, ubiquitous, and probably universal”. Indeed, it has been statistically shown that syntactic analyses of human language ex- hibit a trend for ...
work page 1997
-
[5]
for statistics). Advocates of the projectivity of these languages could say that the theories that cast them as fully projective are “elegant theoretical solutions” (Ninio, 2017). However, such theo- ries could also be seen as a form of observer bias: if projectivity is seen as desirable, be it to ease parsing or for aesthetical considera- tions (Ferrer-i...
work page 2017
-
[6]
or graph-based parsing being outright intractable ex- cept with very simple feature models (McDonald & Satta, 2007). For these reasons, researchers have tried to findmildly non- projectivesets of dependency trees, i.e., sets that are less restric- tive than the set of projective trees, but more restrictive than ar- bitrary non-projectivity. A desirable mi...
work page 2007
-
[7]
A tree that is not ill-nested is said to bewell-nested
if it contains two nodes whose projectionsinterleave, i.e., if there are nodesa,bandi<j<k<lsuch thatiandkare in the projection ofabut not ofb, whereasjandlare in the projection ofband not ofa. A tree that is not ill-nested is said to bewell-nested. In Fig. 3, the bottom tree is ill-nested (the interleaving projections of nodesa andbare highlighted) wherea...
work page 2010
-
[8]
theclass of mildly non-projective trees
under Prague dependen- cies (Hajiˇc et al., 2020), a syntactic theory that prefers function words as heads, in a similar way as Surface-Syntactic Universal Dependencies (SUD) (Gerdes et al., 2018). •WG k is parsable with a dynamic programming algorithm that finds the highest-scoring tree in timeO(n 5+2k) (G ´omez- Rodr´ıguez et al., 2011). WG2 WG1 WG0 Fig...
work page 2020
-
[9]
and O(n5), respectively) and in the case of Mild+1-Inherit trees this comes at almost no cost in empirical coverage, albeit this is no longer the case with gap-minding trees. •Satta & Kuhlmann (2013) add another extra constraint toWG 1, called the head-split property: if the gap in the projection of a node contains the node’s head, then it must also conta...
work page 2013
-
[10]
is shown by Corro (2020): one can implement a variant of theO(n 7)WG 1 parser of (G´omez-Rodr´ıguez et al., 2011), but remove the costliest de- duction rule; which is the complexity bottleneck. Corro shows that this has little effect in coverage while reducing time com- plexity by a factor ofn. The same trick can be applied to mildly ill-nested parsers. A...
work page 2020
-
[11]
1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1-planar 2-planar 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 3-planar Figure 5Multiplanarity. 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...
work page 2009
-
[12]
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. Formal Constraints on Dependency Syntax7 w2 w9 Figure 7Two views of the same 1-Endpoint-Crossing tree. The left view highlights the arcs crossing one given arc (dotted), show- ing that they have the nodew2 in common. The right vie...
work page 2013
-
[13]
(2011), which is a variant of the arc-standard projective parser (Nivre,
and its modified version by Cohen et al. (2011), which is a variant of the arc-standard projective parser (Nivre,
work page 2011
-
[14]
By allowing the transitions to skip overknodes, we obtain the trees of Attardi degreek+1, orAD k+1
which adds transitions that create arcs that “skip” over nodes on the stack (in contrast to arc-standard, which only links adjacent nodes, hence allowing no crossing arcs), while keepingO(n) complexity. By allowing the transitions to skip overknodes, we obtain the trees of Attardi degreek+1, orAD k+1. Much like withk-planarity, in- terest has especially f...
work page 2011
-
[15]
multi-headed withkheads per item
that reduce the complexity to O(n6) while increasing coverage. The sets covered by these algo- rithm variants are also operationally defined. On the other hand, in a separate research line from the Attardi parser, G´omez-Rodr´ıguez et al. (2011) defined a dynamic program- ming parser calledMH k, meaning “multi-headed withkheads per item”, which is a gener...
-
[16]
G´omez-Rodr´ıguez, C., & Nivre, J. (2013). Divisible transition systems and multiplanar dependency parsing.Computational Linguistics, 39(4), 799–845. Retrieved from https://aclanthology.org/J13-4002 doi: 10.1162/COLI a 00150. G´omez-Rodr´ıguez, C., Roca, D., & Vilares, D. (2023). 4 and 7-bit labeling for projective and non-projective dependency trees. In ...
-
[17]
K¨ubler, S., McDonald, R., & Nivre, J. (2009).Depen- dency parsing. Morgan & Claypool, US. Retrieved from 10Formal Constraints on Dependency Syntax /bib/kubler/kubler2009dependency/DependencyParsing.pdf Kuhlmann, M. (2007).Dependency structures and lexicalized gram- mars(Unpublished doctoral dissertation). Saarland University, Saarbr¨ucken, Germany. Kuhlm...
work page 2009
-
[18]
(pp. 177–186). Prague, Czech Republic: Charles University in Prague, Matfyzpress, Prague, Czech Republic. Retrieved from https://aclanthology.org/W13-3720 McDonald, R., Pereira, F ., Ribarov, K., & Haji ˇc, J. (2005). Non-projective dependency parsing using spanning tree algo- rithms. InProceedings of human language technology con- ference and conference ...
-
[19]
doi: 10.1023/A:1008202213790. Yli-Jyr¨a, A. (2003). Multiplanarity – a model for dependency struc- tures in treebanks. In (pp. 189–200). V ¨axj¨o: V ¨axj¨o University Press. Zeman, D., Nivre, J., Abrams, M., Ackermann, E., Aepli, N., Aghaei, H., . . . Ziane, R. (2023).Universal dependencies 2.12.Retrieved from http://hdl.handle.net/11234/1-5150 (LINDAT/CL...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.