Pith. sign in

REVIEW 2 major objections 5 minor 80 references

Memory limitations are hidden in grammar

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Memory limitations are hidden in the formal grammars themselves: uniformly sampled sentences from every tested dependency grammar class have below-chance average dependency distance.

desk verdict A solid computational result about below-chance dependency distances in grammar classes, but the memory-limitation interpretation needs more support than the paper gives it. read the letter →

arxiv 1908.06629 v3 pith:7Y2RL7TM submitted 2019-08-19 cs.CL cs.DM

Carlos Gómez-Rodríguez , Morten H. Christiansen , Ramon Ferrer-i-Cancho This is my paper · ORCID
classification cs.CLcs.DM
keywords dependencygrammardistancememoryconstraintsprojectivetreesmildlynon-projectiverandomlineararrangementcognitiveindependenceuniformsampling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tests the long-standing assumption that formal grammars of human language capture an idealized competence, free of the memory limitations of the human brain. The authors sample billions of sentences uniformly from the spaces defined by several state-of-the-art dependency grammar classes and measure average dependency distance, a standard proxy for memory load. They claim that in every class considered, projective, planar, and three mildly non-projective families, the average dependency distance of artificial structures falls below the random baseline (n+1)/3 for sufficiently large sentence length n. If true, this shows that memory constraints are encoded inside the grammar formalisms themselves, undermining the parsimonious idea that linguistic productivity can be described independently of non-linguistic cognition.

What carries the argument

The central object is the average dependency distance <d>, defined as the mean over dependencies of the linear distance, in number of intermediate words plus one, between a head and its dependent in a dependency tree. The argument compares <d>_AS, the average over uniformly sampled artificial syntactic structures from a given grammar class, with the random linear arrangement baseline <d>_rla = (n+1)/3. The machinery is the uniform sampler over labelled directed trees, built via Prüfer codes and rooting, that produces artificial ensembles for n up to 25, making the comparison free of any direct memory constraint.

What would settle it

A controlled processing experiment could settle the proxy question: if readers show no measurable increase in processing effort, such as reading time, as average dependency distance rises while other factors are held fixed, the proxy fails and the inference from grammar classes to memory constraints collapses. Alternatively, exhibiting a practically motivated mildly non-projective class whose uniform random sample has average dependency distance at or above (n+1)/3 for large n would refute the universality of the effect.

Watch

Extended reading notes

Core claim

The central discovery is that classes of dependency grammars constrain average dependency distance below chance even when no direct memory constraint is imposed. For a sentence of n words, a random linear arrangement of words yields an expected average dependency distance of (n+1)/3; the paper shows that uniformly sampling valid dependency trees from projective, planar, WG1, MH4, MH5, and 1EC classes gives average distances systematically below this baseline for sufficiently large n, with projective and planar classes showing the strongest reduction. The paper interprets this as evidence that memory limitations have permeated grammatical descriptions, making a competence grammar independent of cognitive constraints unlikely.

Load-bearing premise

The entire argument rests on treating average dependency distance as a valid proxy for memory limitations; if dependency distance does not actually track working-memory load during sentence processing, then the below-chance distances in artificial grammar classes would not establish that memory constraints are hidden in grammar.

Editorial extensions

If this is right

  • If correct, the cognitive independence assumption underlying much of generative linguistics loses support: formal grammars are not neutral characterizations of sentencehood but encode memory-related restrictions.
  • The close derivational ties between dependency grammar and categorial, phrase-structure, and minimalist grammars suggest those frameworks likely embed similar hidden constraints, so the finding is not an artifact of one formalism.
  • Language acquisition may be explainable by general cognitive constraints such as working memory rather than language-specific innate grammatical knowledge, because the class of possible structures is already memory-shaped.
  • In language engineering, systems designed to interact with humans may perform better if deliberately constrained to human-like memory limits instead of being given unbounded computational capacity.
  • The result strengthens the view that the scarcity of crossing dependencies in natural language reflects dependency distance minimization, a processing pressure, rather than an arbitrary grammatical rule.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A next step would be to test whether the below-chance effect persists when sampling is weighted by real sentence-length distributions or by attested structures, which would reveal how strong the hidden constraint is relative to actual usage biases.
  • The same uniform-sampling test could be applied to non-dependency formalisms by defining a distance measure on phrase-structure trees, to see whether memory constraints are universal across grammatical frameworks or specific to dependency-based ones.
  • The ordering of distance reduction across classes, projective strongest, then planar, then mildly non-projective, suggests a formal hierarchy of implicit memory cost that could be used to compare parsing algorithms by the load they impose.
  • These results predict that even artificial languages engineered with such grammars, for example in laboratory learning experiments, should show easier processing than surface statistics alone would predict, a directly testable consequence.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper tests the cognitive-independence assumption of formal grammars by computing the average dependency distance <d>_AS of uniformly sampled dependency structures in several grammar classes (projective, planar, WG1, MH4, MH5, and 1EC) for sentence lengths n = 3 to 25. For n ≤ 10 the authors exhaustively enumerate all labelled directed trees; for n > 10 they draw 10^9 uniform random Prüfer-code samples. They report that for all classes considered, <d>_AS falls below the random-linear-arrangement baseline <d>_rla = (n+1)/3 for sufficiently large n, and they interpret this as evidence that memory limitations are inherent to grammatical descriptions. An analysis of attested treebanks (UD, Stanford, Prague) provides a reference curve. The paper concludes that it may be impossible to build a parsimonious theory of human linguistic productivity independent of non-linguistic cognitive constraints.

Significance. If the interpretive step is accepted, the finding would challenge a foundational assumption in linguistics and would have implications for language acquisition, language evolution, and NLP. The study has clear strengths: the exhaustive enumeration for n ≤ 10 is exact, the Prüfer-code sampling is uniform and well described, the data and code are made available, and the 'all structures' class reproduces the known baseline, which is a useful sanity check. The main risk is that the central inference—from below-baseline average dependency distance to memory constraints—is underdetermined. The observed reduction may be a combinatorial consequence of order-sensitive class definitions rather than a specific signature of memory. With additional control analyses or a more carefully scoped conclusion, the contribution would be solid and valuable.

major comments (2)
  1. [p. 5 and Supplementary Text] The paper's central inference from below-baseline <d>_AS to memory constraints depends on the premise that dependency distance is a valid proxy for memory limitations. That premise is asserted with citations (22, 23) but is not derived or validated in this manuscript. Because every class studied is defined by an order-sensitive restriction (planarity forbids crossings, projectivity adds a constraint on the root, WG1 bounds gap degree, MHk bounds multi-headedness, and 1EC bounds endpoint-crossing), the reduction in mean distance could simply be a combinatorial by-product of excluding certain long-distance or crossing configurations from the support. The limitation paragraph on p. 8 addresses the possibility that future classes may not show the effect, but it does not address the possibility that any order-sensitive class with similar restrictions would show it. To make the headline claim load-bearing, the authors should either (i) provide independent evidence for the distance-memory mapping, (ii) include control classes defined by order-sensitive restrictions with no known link to memory and show that they do not show the same drop, or (iii) explicitly rephrase the conclusion as a claim about the combinatorial structure of grammar classes rather than about memory. Without one of these, the conclusion that 'memory limitations have permeated grammatical descriptions' is underdetermined by the data presented.
  2. [Fig. 2B / Fig. 3 / Materials and Methods] The sampled estimates for n > 10 are presented without confidence intervals or standard errors, and some displayed points rest on very few structures (for example, 69 trees for MH5 at n = 25). The statement that <d>_AS is below chance 'for sufficiently large n in all classes' is an asymptotic claim whose tail is supported by these low-count estimates. Please report sampling error (e.g., bootstrap or standard error of the mean), state the effective sample size for each point, and verify that the below-baseline ordering is statistically significant at the displayed points. This is especially important because the main figure suppresses points with fewer than 30 structures, while the text's qualitative claim extends into the regime where counts are small.
minor comments (5)
  1. [p. 8] The phrase 'we cannot not exclude' appears to be a typo for 'we cannot exclude'.
  2. [p. 8] The inline reference '—citeYadav2019a' appears as a broken LaTeX citation and should be replaced with a proper reference.
  3. [One Sentence Summary] The summary says 'Analyses of billions of sentences,' but the artificial structures are not sentences; 'billions of syntactic structures' would be more accurate.
  4. [Materials and Methods] The 30-structure cutoff is justified only by a generic rule of thumb (ref. 46); please provide a more specific justification or a sensitivity analysis for the displayed curves.
  5. [Fig. 2B caption] The caption states that points with fewer than 30 structures are not shown for n > n*, but a reader cannot tell from the figure which classes have sparse points at each n; adding per-point sample sizes or a supplementary table would improve transparency.

Circularity Check

0 steps flagged · score 1.0 of 10

No construction-level circularity; the below-chance mean distances are a new computation from class definitions, with the memory interpretation resting on an external proxy rather than on a fitted input.

full rationale

The derivation chain is not circular at the level of equations. Equation (1) is a combinatorial identity for uniform random linear arrangements and is independently grounded in Jaynes' maximum entropy principle (ref 50), so the citation to the authors' earlier work (ref 25) is not load-bearing. The Methods section proves that the Prüfer-code/random-root procedure generates each labelled directed tree with uniform probability ('each possible directed tree corresponds to exactly one undirected tree... generates each possible directed tree with a uniform probability Kn/n'), so the sampling methodology does not import an unverified result from the authors' prior paper (ref 47). The grammar classes are defined by crossing, gap-degree, and multi-headedness conditions that do not reference dependency distance or memory; the observation that uniform members of these classes have average distance below (n+1)/3 is a nontrivial consequence of those definitions, not a restatement of them. The only point that could look like labeling is the inference from 'distance... as a proxy for memory constraints (22, 23)' to 'memory limitations have permeated grammatical descriptions'; that is an external proxy assumption from the psycholinguistic literature, not a parameter fitted to the data or a self-citation chain. The limitation paragraph on p. 8 addresses class coverage but not the generic-order-constraint alternative, and the unresolved 'citeYadav2019a' placeholder is a missing-reference artifact; neither is a circular step. Self-citations appear as supporting context (e.g., refs 13, 29, 30, 34), but none is the load-bearing premise of the new computation. Therefore no circular step is exhibited; score 1 reflects minor, non-load-bearing self-citation and the interpretive proxy step, not a reduction of the result to its inputs.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central computational result does not rest on fitted parameters, but it does rely on the standard uniform-tree sampling, the (n+1)/3 baseline, the domain assumption that dependency distance proxies memory load, and the representativeness of the chosen grammar classes. The threshold values (n*=10, S=10^9, display minimum 30) are hand-picked computational choices.

free parameters (3)
  • n* = 10
    Cutoff between exhaustive enumeration and random sampling; chosen for computational tractability, not fitted to data.
  • S = 1e9
    Number of random trees sampled per length for n>10; chosen for computational tractability.
  • display minimum sample size = 30
    Only class-length combinations with at least 30 sampled structures are shown in Figure 2B; a rule-of-thumb threshold from ref 46, which could mask instability at small sample sizes.
assumptions (4)
  • standard math Uniform sampling of labeled directed trees can be achieved by generating a uniformly random Prüfer code and then choosing a root uniformly at random.
    Used in Methods to generate artificial syntactic structures; follows from Cayley's formula and the bijection between directed trees and (undirected tree, root) pairs.
  • standard math The expected dependency distance under a random linear arrangement of words in a sentence of length n is (n+1)/3.
    Serves as the chance baseline in Eq. 1; standard result from random permutations, cited to ref 25 and justified in the supplementary text.
  • domain assumption The distance between syntactically related words is a valid proxy for memory constraints in sentence processing.
    Central interpretive premise; cited to refs 22 and 23, but treated as given rather than tested in this paper.
  • domain assumption The selected grammar classes (projective, planar, WG1, MH4, MH5, 1EC) represent the state of the art in dependency-based formal grammars.
    Used to generalize the finding to 'parsimonious grammatical frameworks'; the paper acknowledges this in its limitations paragraph.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Memory limitations are hidden in grammar." pith.science (2026). https://pith.science/paper/7Y2RL7TM

@misc{pith2026190806629,
  author       = {Pith},
  title        = {Pith review of: Memory limitations are hidden in grammar},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7Y2RL7TM}},
  note         = {Machine review of arXiv:1908.06629}
}
read the original abstract

The ability to produce and understand an unlimited number of different sentences is a hallmark of human language. Linguists have sought to define the essence of this generative capacity using formal grammars that describe the syntactic dependencies between constituents, independent of the computational limitations of the human brain. Here, we evaluate this independence assumption by sampling sentences uniformly from the space of possible syntactic structures. We find that the average dependency distance between syntactically related words, a proxy for memory limitations, is less than expected by chance in a collection of state-of-the-art classes of dependency grammars. Our findings indicate that memory limitations have permeated grammatical descriptions, suggesting that it may be impossible to build a parsimonious theory of human linguistic productivity independent of non-linguistic cognitive constraints.

Figures

Figures reproduced from arXiv: 1908.06629 by the authors.

Figure 1
Figure 1. Examples of syntactic dependency structures. Arcs indicate syntactic dependencies [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The average dependency length, hdi, as a function of n, the sentence length (in words). For reference, the baseline defined by a random linear arrangement of the words of the sentence, hdi rla is also shown (dashed line). A. Attested syntactic dependency trees (RS) following three different annotation criteria: UD, Prague and Stanford dependencies. B. Arti￾ficial syntactic dependency structures (AS) belonging to dif… view at source ↗
Figure 3
Figure 3. Undersampling in artificial syntactic dependency structures (AS). A. [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: A. A tree that is planar (dependencies do not cross) but not projective (the root node, [PITH_FULL_IMAGE:figures/full_fig_p026_4.png]
Figure 5
Figure 5. Figure 5: A. An ill-nested tree (the yields of node 3—circled—and node 4–squared—form [PITH_FULL_IMAGE:figures/full_fig_p027_5.png]
Figure 6
Figure 6. Figure 6: A. An 1-Endpoint-Crossing tree (given any dependency, dependencies crossing it are [PITH_FULL_IMAGE:figures/full_fig_p028_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

80 extracted references · 80 canonical work pages

  1. [1]

    Chomsky, Aspects of the theory of syntax (MIT Press, Cambridge, MA, 1965)

    N. Chomsky, Aspects of the theory of syntax (MIT Press, Cambridge, MA, 1965)

    work page 1965

  2. [2]

    Miller, Strong generative capacity: The semantics of linguistic formalism (Cambridge University Press, Cambridge, UK, 2000)

    P. Miller, Strong generative capacity: The semantics of linguistic formalism (Cambridge University Press, Cambridge, UK, 2000)

    work page 2000

  3. [3]

    Bod, A New History of the Humanities: The Search for Principles and Patterns from Antiquity to the Present (Oxford University Press, Oxford, UK, 2013)

    R. Bod, A New History of the Humanities: The Search for Principles and Patterns from Antiquity to the Present (Oxford University Press, Oxford, UK, 2013)

    work page 2013

  4. [4]

    M. D. Hauser, N. Chomsky, W. T. Fitch, Science 298, 1569 (2002)

    work page 2002

  5. [5]

    Pinker, Language evolution, M

    S. Pinker, Language evolution, M. H. Christiansen, S. Kirby, eds. (Oxford University Press, New York, 2003), pp. 16–37

    work page 2003

  6. [6]

    Klein, C

    D. Klein, C. D. Manning, Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL) (2003), pp. 423–430. 10

    work page 2003

  7. [7]

    C. Dyer, A. Kuncoro, M. Ballesteros, N. A. Smith, Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies(Association for Computational Linguistics, San Diego, California, 2016), pp. 199–209

    work page 2016

  8. [8]

    G ´omez-Rodr´ıguez, T

    C. G ´omez-Rodr´ıguez, T. Shi, L. Lee,Proceedings of the 56th Annual Meeting of the Asso- ciation for Computational Linguistics (Volume 1: Long Papers)(Association for Computa- tional Linguistics, Melbourne, Australia, 2018), pp. 2663–2674

    work page 2018

Show all 80 references
  1. [9]

    Morrill, Categorial grammar: logical syntax, semantics, and processing (Oxford Uni- versity Press, Oxford, 2010)

    G. Morrill, Categorial grammar: logical syntax, semantics, and processing (Oxford Uni- versity Press, Oxford, 2010)

    2010

  2. [10]

    J. A. Hawkins, Efficiency and Complexity in Grammars (Oxford University Press, Oxford, 2004)

    2004

  3. [11]

    E. M. Gold, Information and Control 10, 447 (1967)

    1967

  4. [12]

    M. H. Christiansen, N. Chater, Behavioral and Brain Sciences 31, 489 (2008)

    2008

  5. [13]

    G ´omez-Rodr´ıguez, R

    C. G ´omez-Rodr´ıguez, R. Ferrer-i-Cancho,Physical Review E 96, 062304 (2017)

    2017

  6. [14]

    Nivre, Dependency grammar and dependency parsing, Tech

    J. Nivre, Dependency grammar and dependency parsing, Tech. Rep. MSI 05133 , V ¨axj¨o University, School of Mathematics and Systems Engineering (2005)

    2005

  7. [15]

    J. Nivre, Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1 - Volume 1, ACL ’09 (Association for Computational Linguistics, Stroudsburg, PA, USA, 2009), pp. 351–359

    2009

  8. [16]

    T. Groß, T. Osborne, SKY Journal of Linguistics 22, 43 (2009). 11

    2009

  9. [17]

    Barth ´elemy, Morphogenesis of Spatial Networks (Springer, Cham, Switzerland, 2018)

    M. Barth ´elemy, Morphogenesis of Spatial Networks (Springer, Cham, Switzerland, 2018)

    2018

  10. [18]

    Gaifman, Information and Control 8, 304 (1965)

    H. Gaifman, Information and Control 8, 304 (1965)

    1965

  11. [19]

    Kahane, N

    S. Kahane, N. Mazziotta, Proceedings of the 14th Meeting on the Mathematics of Language (MoL 2015) (Association for Computational Linguistics, Chicago, USA, 2015), pp. 152– 164

    2015

  12. [20]

    Osborne, M

    T. Osborne, M. Putnam, T. Gross, The Linguistic Review 28, 315364 (2011)

    2011

  13. [21]

    K ¨ubler, R

    S. K ¨ubler, R. McDonald, J. Nivre, Dependency Parsing (Morgan and Claypool, 2009)

    2009

  14. [22]

    H. Liu, C. Xu, J. Liang, Physics of Life Reviews 21, 171 (2017)

    2017

  15. [23]

    Temperley, D

    D. Temperley, D. Gildea, Annual Review of Linguistics 4, 67 (2018)

    2018

  16. [24]

    Roark, M

    B. Roark, M. Mitchell, J. Hosom, K. Hollingshead, J. Kaye, IEEE Transactions on Audio, Speech, and Language Processing 19, 2081 (2011)

    2011

  17. [25]

    Ferrer-i-Cancho, Physical Review E 70, 056135 (2004)

    R. Ferrer-i-Cancho, Physical Review E 70, 056135 (2004)

    2004

  18. [26]

    Liu, Journal of Cognitive Science 9, 159 (2008)

    H. Liu, Journal of Cognitive Science 9, 159 (2008)

    2008

  19. [27]

    Albert Park, R

    Y . Albert Park, R. Levy, Proceedings of the 10th Annual Meeting of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT) conference (Association for Computational Linguistics, Stroudsburg, PA, USA, 2009), pp. 335–343

    2009

  20. [28]

    Futrell, K

    R. Futrell, K. Mahowald, E. Gibson, Proceedings of the National Academy of Sciences112, 10336 (2015)

    2015

  21. [29]

    Ferrer-i-Cancho, C

    R. Ferrer-i-Cancho, C. G ´omez-Rodr´ıguez,Journal of Quantitative Linguistics p. in press (2019). 12

    2019

  22. [30]

    Ferrer-i-Cancho, Europhysics Letters 76, 1228 (2006)

    R. Ferrer-i-Cancho, Europhysics Letters 76, 1228 (2006)

    2006

  23. [31]

    Ferrer-i-Cancho, Advances in Complex Systems 11, 393 (2008)

    R. Ferrer-i-Cancho, Advances in Complex Systems 11, 393 (2008)

    2008

  24. [32]

    Ferrer-i-Cancho, H

    R. Ferrer-i-Cancho, H. Liu, Glottotheory 5, 143 (2014)

    2014

  25. [33]

    G ´omez-Rodr´ıguez,Computational Linguistics 42, 809 (2016)

    C. G ´omez-Rodr´ıguez,Computational Linguistics 42, 809 (2016)

    2016

  26. [34]

    Ferrer-i-Cancho, C

    R. Ferrer-i-Cancho, C. G ´omez-Rodr´ıguez,Complexity 21, 320 (2016)

    2016

  27. [35]

    Alemany-Puig, Edge crossings in linear arrangements: from theory to algorithms and applications, Master’s thesis, Barcelona School of Informatics (2019)

    L. Alemany-Puig, Edge crossings in linear arrangements: from theory to algorithms and applications, Master’s thesis, Barcelona School of Informatics (2019)

    2019

  28. [36]

    Tomasello, Constructing a language

    M. Tomasello, Constructing a language. A usage-based theory of language acquisition (Harvard University Press, Cambridge, MA, 2005)

    2005

  29. [37]

    Nivre, M

    J. Nivre, M. Abrams, ˇZ. Agi´c, et al., Universal dependencies 2.4 (2019). LINDAT/CLARIN digital library at the Institute of Formal and Applied Linguistics ( ´UFAL), Faculty of Math- ematics and Physics, Charles University

    2019

  30. [38]

    de Marneffe, C

    M.-C. de Marneffe, C. D. Manning, COLING 2008: Proceedings of the workshop on Cross- Framework and Cross-Domain Parser Evaluation(COLING 2008 Organizing Committee, 2008), pp. 1–8

    2008

  31. [39]

    Bresnan, Lexical-Functional Syntax (Blackwell, Chichester, United Kingdom, 2000)

    J. Bresnan, Lexical-Functional Syntax (Blackwell, Chichester, United Kingdom, 2000)

    2000

  32. [40]

    Rosa, et al., Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14), N

    R. Rosa, et al., Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14), N. C. C. Chair), et al., eds. (European Language Resources Association (ELRA), Reykjavik, Iceland, 2014). 13

    2014

  33. [41]

    de Marneffe, et al., Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14), N

    M.-C. de Marneffe, et al., Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14), N. C. C. Chair), et al., eds. (European Language Resources Association (ELRA), Reykjavik, Iceland, 2014)

    2014

  34. [42]

    Haji ˇc, et al., Prague dependency treebank 2.0, CDROM CAT: LDC2006T01, ISBN 1- 58563-370-4

    J. Haji ˇc, et al., Prague dependency treebank 2.0, CDROM CAT: LDC2006T01, ISBN 1- 58563-370-4. Linguistic Data Consortium (2006)

    2006

  35. [43]

    Sgall, A functional approach to syntax in generative description of language (Elsevier, 1969)

    P. Sgall, A functional approach to syntax in generative description of language (Elsevier, 1969)

    1969

  36. [44]

    Hajicova, Concise History of the Language Sciences, E

    E. Hajicova, Concise History of the Language Sciences, E. Koerner, R. Asher, eds. (Perga- mon, Amsterdam, 1995), pp. 253 – 262

    1995

  37. [45]

    M. C. Passarotti, L’analisi Linguistica e Letteraria1, 21 (2016)

    2016

  38. [46]

    R. V . Hogg, E. A. Tanis,Probability and Statistical Inference (Prentice Hall, Upper Saddle River, NJ, 1997), 7th edn

    1997

  39. [47]

    J. L. Esteban, R. Ferrer-i-Cancho, C. G ´omez-Rodr´ıguez,Journal of Statistical Mechanics p. 063401 (2016)

    2016

  40. [48]

    Pr ¨ufer, Arch

    H. Pr ¨ufer, Arch. Math. Phys 27, 742 (1918)

    1918

  41. [49]

    Cayley, Quart

    A. Cayley, Quart. J. Math 23, 376 (1889)

  42. [50]

    H. K. Kesavan, Jaynes’ maximum entropy principle(Springer US, Boston, MA, 2009), pp. 1779–1782

    2009

  43. [51]

    Gildea, D

    D. Gildea, D. Temperley, Cognitive Science 34, 286 (2010)

    2010

  44. [52]

    Ferrer-i-Cancho, C

    R. Ferrer-i-Cancho, C. G ´omez-Rodr´ıguez,Glottometrics 33, 33 (2016). 14

    2016

  45. [53]

    M. H. Christiansen, N. Chater, Cognitive Science 23, 157 (1999)

    1999

  46. [54]

    Ferrer-i-Cancho, Glottometrics 25, 1 (2013)

    R. Ferrer-i-Cancho, Glottometrics 25, 1 (2013)

    2013

  47. [55]

    G ´omez-Rodr´ıguez, J

    C. G ´omez-Rodr´ıguez, J. Nivre,Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, ACL ’10 (2010), pp. 1492–1501

    2010

  48. [56]

    Yli-Jyr ¨a, C

    A. Yli-Jyr ¨a, C. G ´omez-Rodr´ıguez,Proceedings of the 55th Annual Meeting of the Associ- ation for Computational Linguistics (Volume 1: Long Papers) (Association for Computa- tional Linguistics, Vancouver, Canada, 2017), pp. 1745–1755

    2017

  49. [57]

    Kuhlmann, P

    M. Kuhlmann, P. Jonsson, Transactions of the Association for Computational Linguistics 3, 559 (2015)

    2015

  50. [58]

    Nivre, Proceedings of the 8th International Workshop on Parsing Technologies (IWPT) (2003), pp

    J. Nivre, Proceedings of the 8th International Workshop on Parsing Technologies (IWPT) (2003), pp. 149–160

    2003

  51. [59]

    Nivre, Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together (ACL)(2004), pp

    J. Nivre, Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together (ACL)(2004), pp. 50–57

    2004

  52. [60]

    J. Nivre, Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP (ACL-IJCNLP) (2009), pp. 351–359

    2009

  53. [61]

    M. A. Covington, Proceedings of the 39th Annual ACM Southeast Conference (2001), pp. 95–102

    2001

  54. [62]

    D. Chen, C. Manning, Proceedings of the 2014 Conference on Empirical Methods in Nat- ural Language Processing (EMNLP) (Doha, Qatar, 2014), pp. 740–750. 15

    2014

  55. [63]

    C. Dyer, M. Ballesteros, W. Ling, A. Matthews, N. A. Smith, Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) (Association for Computational ...

    2015

  56. [64]

    Ferrer-i-Cancho, C

    R. Ferrer-i-Cancho, C. G ´omez-Rodr´ıguez, J. L. Esteban,Physica A: Statistical Mechanics and its Applications 493, 311 (2018)

    2018

  57. [65]

    Kuhlmann, J

    M. Kuhlmann, J. Nivre, Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions (2006), pp. 507–514

    2006

  58. [66]

    Bodirsky, M

    M. Bodirsky, M. Kuhlmann, M. M¨ohl, 10th Conference on Formal Grammar and 9th Meet- ing on Mathematics of Language (Edinburgh, Scotland, UK, 2005)

    2005

  59. [67]

    Kuhlmann, Dependency Structures and Lexicalized Grammars

    M. Kuhlmann, Dependency Structures and Lexicalized Grammars. An Algebraic Approach, vol. 6270 of Lecture Notes in Computer Science (Springer, 2010)

    2010

  60. [68]

    G ´omez-Rodr´ıguez, D

    C. G ´omez-Rodr´ıguez, D. Weir, J. Carroll, Proceedings of the 12th Conference of the Eu- ropean Chapter of the Association for Computational Linguistics (EACL-09) (2009), pp. 291–299

    2009

  61. [69]

    G ´omez-Rodr´ıguez, J

    C. G ´omez-Rodr´ıguez, J. Carroll, D. Weir,Computational Linguistics 37, 541 (2011)

    2011

  62. [70]

    Corro, J

    C. Corro, J. Le Roux, M. Lacroix, A. Rozenknop, R. Wolfler Calvo, Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (Association for Computational Linguistics, Berlin, Germany, 2016), pp. 355–366

    2016

  63. [71]

    Pitler, S

    E. Pitler, S. Kannan, M. Marcus, Transactions of the Association of Computational Lin- guistics 1, 13 (2013)

    2013

  64. [72]

    Stanford

    E. Pitler, Transactions of the Association for Computational Linguistics 2, 41 (2014). 16 Acknowledgments We thank two anonymous reviewers from Science for their many suggestions to improve the article. We are also to L. Alemany-Puig, A. Hernandez-Fernandez and M. Vitevitch fo...

    2014

  65. [73]

    It is known that T (n) = nn−2 (49)

    Generating all the T (n) labelled (undirected) trees of n vertices using Pr¨ufer codes (48). It is known that T (n) = nn−2 (49)

  66. [74]

    A rooting consists in choosing one node of the tree as the root, and making all edges point away from the root via a depth-first traversal

    Converting each of these random trees into labelled directed trees (i.e., dependency trees) by rooting it in all possible ways. A rooting consists in choosing one node of the tree as the root, and making all edges point away from the root via a depth-first traversal. This produ...

  67. [75]

    Producing a syntactic dependency structure from every directed tree using vertex labels (integers from 1 to n) as vertex positions in a linear arrangement (47)

  68. [76]

    The random sampling version consists of

    Discarding the trees that do not belong to the target class. The random sampling version consists of

  69. [77]

    Generating S uniformly random labelled (undirected) trees of n vertices, via uniformly random Pr¨ufer codes (48)

  70. [78]

    This produces S syntactic dependency structures

    Converting these uniformly random labelled trees to uniformly random labelled directed trees (i.e., dependency trees) by randomly choosing one node of each tree as the root, and making all edges point away from the root via a depth-first traversal. This produces S syntactic dep...

  71. [79]

    Same as exhaustive version

  72. [80]

    Same as exhaustive version. Note that Step 2 warrants that labelled directed trees in the ensemble are uniformly random: if we call Kn the probability of generating each undirected tree ofn vertices with a random Pr¨ufer 23 code, we can observe that each possible directed tree...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.