Scientific publications

@article{Petrini2022c,

title = {The distribution of syntactic dependency distances},

author = {Sonia Petrini and Ramon Ferrer-i-Cancho},

url = {https://arxiv.org/abs/2211.14620},

doi = {10.53482/2025_58_424},

year  = {2025},

date = {2025-01-01},

journal = {Glottometrics},

volume = {58},

pages = {35-94},

abstract = {The syntactic structure of a sentence can be represented as a graph, where vertices are words and edges indicate syntactic dependencies between them. In this setting, the distance between two linked words is defined as the difference between their positions. Here we wish to contribute to the characterization of the actual distribution of syntactic dependency distances, which has previously been argued to follow a power-law distribution. Here we propose a new model with two exponential regimes in which the probability decay is allowed to change after a break-point. This transition could mirror the transition from the processing of word chunks to higher-level structures. We find that a two-regime model - where the first regime follows either an exponential or a power-law decay - is the most likely one in all 20 languages we considered, independently of sentence length and annotation style. Moreover, the break-point exhibits low variation across languages and averages values of 4-5 words, suggesting that the amount of words that can be simultaneously processed abstracts from the specific language to a high degree. The probability decay slows down after the breakpoint, consistently with a universal chunk-and-pass mechanism. Finally, we give an account of the relation between the best estimated model and the closeness of syntactic dependencies as function of sentence length, according to a recently introduced optimality score.},

keywords = {dependency syntax, network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2023b,

title = {The optimal placement of the head in the noun phrase. The case of demonstrative, numeral, adjective and noun},

author = {R. Ferrer-i-Cancho},

url = {https://arxiv.org/abs/2402.10311},

doi = {10.1080/09296174.2024.2400847},

year  = {2024},

date = {2024-01-01},

journal = {Journal of Quantitative Linguistics},

volume = {32},

number = {1},

pages = {26-53},

abstract = {The word order of a sentence is shaped by multiple principles. The principle of syntactic dependency distance minimization is in conflict with the principle of surprisal minimization (or predictability maximization) in single head syntactic dependency structures: while the former predicts that the head should be placed at the center of the linear arrangement, the latter predicts that the head should be placed at one of the ends (either first or last). A critical question is when surprisal minimization (or predictability maximization) should surpass syntactic dependency distance minimization. In the context of single head structures, it has been predicted that this is more likely to happen when two conditions are met, i.e. (a) fewer words are involved and (b) words are shorter. Here we test the prediction on the noun phrase when it is composed of a demonstrative, a numeral, an adjective and a noun. We find that, across preferred orders in languages, the noun tends to be placed at one of the ends, confirming the theoretical prediction. We also show evidence of anti locality effects: syntactic dependency distances in preferred orders are longer than expected by chance.},

keywords = {word order, Zipf's law of abbreviation},

pubstate = {published},

tppubtype = {article}

}

@article{Alemany2022b,

title = {The Maximum Linear Arrangement Problem for trees under projectivity and planarity},

author = {L. Alemany-Puig and J. L. Esteban and R. Ferrer-i-Cancho},

url = {https://arxiv.org/abs/2206.06924},

doi = {10.1016/j.ipl.2023.106400},

year  = {2024},

date = {2024-01-01},

journal = {Information Processing Letters},

volume = {183},

pages = {106400},

abstract = {The Maximum Linear Arrangement problem (MaxLA) consists of finding a mapping π from the n vertices of a graph G to distinct consecutive integers that maximizes the sum of edge lengths. In this setting, vertices are considered to lie on a horizontal line and edges are drawn as semicircles above the line. There exist variants of MaxLA in which the arrangements are constrained. In the planar variant edge crossings are forbidden. In the projective variant for rooted trees arrangements are planar and the root cannot be covered by any edge. Here we present O(n)-time and O(n)-space algorithms that solve Planar and Projective MaxLA for trees. We also prove several properties of maximum projective and planar arrangements.},

keywords = {dependency syntax, network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Alemany2022c,

title = {The expected sum of edge lengths in planar linearizations of trees},

author = {L. Alemany-Puig and R. Ferrer-i-Cancho},

url = {https://arxiv.org/abs/2207.05564},

doi = {10.15398/jlm.v12i1.362},

year  = {2024},

date = {2024-01-01},

journal = {Journal of Language Modelling},

volume = {12},

number = {1},

pages = {1-42},

abstract = {Dependency graphs have proven to be a very successful model to represent the syntactic structure of sentences of human languages. In these graphs, widely accepted to be trees, vertices are words and arcs connect syntactically-dependent words. The tendency of these dependencies to be short has been demonstrated using random baselines for the sum of the lengths of the edges or its variants. A ubiquitous baseline is the expected sum in projective orderings (wherein edges do not cross and the root word of the sentence is not covered by any edge). It was shown that said expected value can be computed in O(n) time. In this article we focus on planar orderings (where the root word can be covered) and present two main results. First, we show the relationship between the expected sum in planar arrangements and the expected sum in projective arrangements. Second, we also derive a O(n)-time algorithm to calculate the expected value of the sum of edge lengths. These two results stem from another contribution of the present article, namely a characterization of planarity that, given a sentence, yields either the number of planar permutations or an efficient algorithm to generate uniformly random planar permutations of the words. Our research paves the way for replicating past research on dependency distance minimization using random planar linearizations as random baseline.},

keywords = {dependency syntax, network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Alemany2023a,

title = {On the maximum linear arrangement problem for trees},

author = {L. Alemany-Puig and J. L. Esteban and R. Ferrer-i-Cancho},

url = {https://arxiv.org/abs/2312.04487},

year  = {2023},

date = {2023-01-01},

abstract = {Linear arrangements of graphs are a well-known type of graph labeling and are found at the heart of many important computational problems, such as the Minimum Linear Arrangement Problem (minLA). A linear arrangement is usually defined as a permutation of the n vertices of a graph. An intuitive geometric setting is that of vertices lying on consecutive integer positions in the real line, starting at 1; edges are typically drawn as semicircles above the real line. In this paper we study the Maximum Linear Arrangement problem (MaxLA), the maximization variant of minLA and a less studied problem than minLA. We a devise new characterization of maximum arrangements of general graphs, and prove that MaxLA can be solved for cycle graphs in constant time, and for k-linear trees (k≤2) in time O(n). We present a simple algorithm that solves a constrained variant of MaxLA, which we call bipartite MaxLA, in time O(n). This algorithm has two promising characteristics. First, it solves MaxLA for most trees consisting of a few tenths of nodes. Second, it produces a high quality approximation to MaxLA for trees where the algorithm fails to solve MaxLA. Furthermore, we conjecture this algorithm solves MaxLA for at least 50% of all free trees.},

keywords = {dependency syntax, network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2023a,

title = {Swap distance minimization in SOV languages. Cognitive and mathematical foundations},

author = {R. Ferrer-i-Cancho and S. Namboodiripad},

url = {http://arxiv.org/abs/2312.04219},

doi = {10.53482/2023_55_412},

year  = {2023},

date = {2023-01-01},

journal = {Glottometrics},

volume = {55},

pages = {59-88},

abstract = {Distance minimization is a general principle of language. A special case of this principle in the domain of word order is swap distance minimization. This principle predicts that variations from a canonical order that are reached by fewer swaps of adjacent constituents are lest costly and thus more likely. Here we investigate the principle in the context of the triple formed by subject (S), object (O) and verb (V). We introduce the concept of word order rotation as a cognitive underpinning of that prediction. When the canonical order of a language is SOV, the principle predicts SOV < SVO, OSV < VSO, OVS < VOS, in order of increasing cognitive cost. We test the prediction in three flexible order SOV languages: Korean (Koreanic), Malayalam (Dravidian), and Sinhalese (Indo-European). Evidence of swap distance minimization is found in all three languages, but it is weaker in Sinhalese. Swap distance minimization is stronger than a preference for the canonical order in Korean and especially Malayalam.},

keywords = {word order},

pubstate = {published},

tppubtype = {article}

}

@article{Alemany2021b,

title = {Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees},

author = {L. Alemany-Puig and R. Ferrer-i-Cancho},

url = {https://arxiv.org/abs/2107.03277},

doi = {10.1162/coli_a_00442},

year  = {2022},

date = {2022-01-01},

journal = {Journal of Computational Linguistics},

volume = {48},

number = {3},

pages = {491–516},

abstract = {The syntactic structure of a sentence is often represented using syntactic dependency trees. The sum of the distances between syntactically related words has been in the limelight for the past decades. Research on dependency distances led to the formulation of the principle of dependency distance minimization whereby words in sentences are ordered so as to minimize that sum. Numerous random baselines have been defined to carry out related quantitative studies on languages. The simplest random baseline is the expected value of the sum in unconstrained random permutations of the words in the sentence, namely when all the shufflings of the words of a sentence are allowed and equally likely. Here we focus on a popular baseline: random projective permutations of the words of the sentence, that is, permutations where the syntactic dependency structure is projective, a formal constraint that sentences satisfy often in languages. Thus far, the expectation of the sum of dependency distances in random projective shufflings of a sentence has been estimated approximately with a Monte Carlo procedure whose cost is of the order of Zn, where n is the number of words of the sentence and Z is the number of samples; the larger Z, the lower the error of the estimation but the larger the time cost. Here we present formulae to compute that expectation without error in time of the order of n. Furthermore, we show that star trees maximize it, and devise a dynamic programming algorithm to retrieve the trees that minimize it.},

keywords = {dependency syntax, network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Alemany2021a,

title = {Minimum projective linearizations of trees in linear time},

author = {L. Alemany-Puig and J. L. Esteban and R. Ferrer-i-Cancho},

url = {https://arxiv.org/abs/2102.03277},

doi = {10.1016/j.ipl.2021.106204},

year  = {2022},

date = {2022-01-01},

journal = {Information Processing Letters},

volume = {174},

pages = {106204},

abstract = {The minimum linear arrangement problem (MLA) consists of finding a mapping π from vertices of a graph to integers that minimizes the sum of dependency distances. For trees, various algorithms are available to solve the problem in polynomial time; the best known runs in subquadratic time in n=|V|. There exist variants of the MLA in which the arrangements are constrained to certain classes of projectivity. Iordanskii, and later Hochberg and Stallmann (HS), put forward O(n)-time algorithms that solve the problem when arrangements are constrained to be planar. We also consider linear arrangements of rooted trees that are constrained to be projective. Gildea and Temperley (GT) sketched an algorithm for the projectivity constraint which, as they claimed, runs in O(n) but did not provide any justification of its cost. In contrast, Park and Levy claimed that GT's algorithm runs in O(n log d_max) where dmax is the maximum degree but did not provide sufficient detail. Here we correct an error in HS's algorithm for the planar case, show its relationship with the projective case, and derive an algorithm for the projective case that runs undoubtlessly in O(n)-time.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2020b,

title = {Optimality of syntactic dependency distances},

author = {R. Ferrer-i-Cancho and C. Gómez-Rodríguez and J. L. Esteban and L. Alemany-Puig},

url = {https://arxiv.org/abs/2007.15342},

doi = {10.1103/PhysRevE.105.014308},

year  = {2022},

date = {2022-01-01},

journal = {Physical Review E},

volume = {105},

pages = {014308},

abstract = {It is often stated that human languages, as other biological systems, are shaped by cost-cutting pressures but, to what extent? Attempts to quantify the degree of optimality of languages by means of an optimality score have been scarce and focused mostly on English. Here we recast the problem of the optimality of the word order of a sentence as an optimization problem on a 

spatial network where the vertices are words, arcs indicate syntactic dependencies and the space is defined by the linear order of the words in the sentence. We introduce a new score to quantify the cognitive pressure to reduce the distance between linked words in a sentence. The analysis of sentences from 93 languages representing 19 linguistic families reveals that half of languages are optimized to a 70% or more. The score indicates that distances are not significantly reduced in a few languages and confirms two theoretical predictions, i.e. that longer sentences are more optimized and that distances are more likely to be longer than expected by chance in short sentences. We 

present a new hierarchical ranking of languages by their degree of optimization. The statistical advantages of the new score call for a reevaluation of the evolution of dependency distance over time in languages as well as the relationship between dependency distance and linguistic competence. Finally, the principles behind the design of the score can be extended to develop more powerful normalizations of topological distances or physical distances in more dimensions.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Gomez2019a,

title = {Memory limitations are hidden in grammar},

author = {C. Gómez-Rodríguez and M. H. Christiansen and R. Ferrer-i-Cancho},

url = {https://arxiv.org/abs/1908.06629},

doi = {10.53482/2022_52_397},

year  = {2022},

date = {2022-01-01},

journal = {Glottometrics},

volume = {52},

pages = {39 – 64},

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.},

keywords = {dependency syntax, network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2019a,

title = {Anti dependency distance minimization in short sequences. A graph theoretic approach},

author = {R. Ferrer-i-Cancho and C. Gómez-Rodríguez},

url = {https://arxiv.org/abs/1906.05765},

doi = {10.1080/09296174.2019.1645547},

year  = {2021},

date = {2021-01-01},

journal = {Journal of Quantitative Linguistics},

volume = {28},

number = {1},

pages = {50-76},

abstract = {Dependency distance minimization (DDm) is a word order principle favouring the placement of syntactically related words close to each other in sentences. Massive evidence of the principle has been reported for more than a decade with the help of syntactic dependency treebanks where long sentences abound. However, it has been predicted theoretically that the principle is more likely to be beaten in short sequences by the principle of surprisal minimization (predictability maximization). Here we introduce a simple binomial test to verify such a hypothesis. In short sentences, we find anti-DDm for some languages from different families. Our analysis of the syntactic dependency structures suggests that anti-DDm is produced by star trees.},

note = {published online in 2019},

keywords = {word order},

pubstate = {published},

tppubtype = {article}

}

@article{Alemany2019b,

title = {Fast calculation of the variance of edge crossings in random linear arrangements},

author = {L. Alemany-Puig and R. Ferrer-i-Cancho},

url = {https://arxiv.org/abs/2003.03258},

year  = {2020},

date = {2020-01-01},

pages = {under review},

abstract = {The interest in spatial networks where vertices are embedded in a one-dimensional space is growing. Remarkable examples of these networks are syntactic dependency trees and RNA structures. In this setup, the vertices of the network are arranged linearly and then edges may cross when drawn above the sequence of vertices. Recently, two aspects of the distribution of the number of crossings in uniformly random linear arrangements have been investigated: the expectation and the variance. While the computation of the expectation is straightforward, that of the variance is not. Here we present fast algorithms to calculate that variance in arbitrary graphs and forests. As for the latter, the algorithm calculates variance in linear time with respect to the number of vertices. This paves the way for many applications that rely on an exact but fast calculation of that variance. These algorithms are based on novel arithmetic expressions for the calculation of the variance that we develop from previous theoretical work.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Alemany2018a,

title = {Edge crossings in random linear arrangements},

author = {L. Alemany-Puig and R. Ferrer-i-Cancho},

doi = {10.1088/1742-5468/ab6845},

year  = {2020},

date = {2020-01-01},

journal = {Journal of Statistical Mechanics},

number = {2},

pages = {023403},

abstract = {In spatial networks vertices are arranged in some space and edges may cross. When arranging vertices in a 1D lattice edges may cross when drawn above the vertex sequence as it happens in linguistic and biological networks. Here we investigate the general problem of the distribution of edge crossings in random arrangements of the vertices. We generalize the existing formula for the expectation of this number in random linear arrangements of trees to any network and derive an expression for the variance of the number of crossings in an arbitrary layout relying on a novel characterization of the algebraic structure of that variance in an arbitrary space. We provide compact formulae for the expectation and the variance in complete graphs, complete bipartite graphs, cycle graphs, one-regular graphs and various kinds of trees (star trees, quasi-star trees and linear trees). In these networks, the scaling of expectation and variance as a function of network size is asymptotically power-law-like in random linear arrangements. Our work paves the way for further research and applications in one-dimension or investigating the distribution of the number of crossings in lattices of higher dimension or other embeddings.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2017a,

title = {Are crossing dependencies really scarce?},

author = {R. Ferrer-i-Cancho and C. Gómez-Rodríguez and J. L. Esteban},

doi = {10.1016/j.physa.2017.10.048},

year  = {2018},

date = {2018-01-01},

journal = {Physica A},

volume = {493},

pages = {311-329},

abstract = {The syntactic structure of a sentence can be modelled as a tree, where vertices correspond to words and edges indicate syntactic dependencies. It has been claimed recurrently that the number of edge crossings in real sentences is small. However, a baseline or null hypothesis has been lacking. Here we quantify the amount of crossings of real sentences and compare it to the predictions of a series of baselines. We conclude that crossings are really scarce in real sentences. Their scarcity is unexpected by the hubiness of the trees. Indeed, real sentences are close to linear trees, where the potential number of crossings is maximized.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Chen2018a,

title = {A dependency look at the reality of constituency},

author = {X. Chen and C. C. Gómez-Rodríguez and R. Ferrer-i-Cancho},

url = {http://hdl.handle.net/2117/117466},

year  = {2018},

date = {2018-01-01},

journal = {Glottometrics},

volume = {40},

pages = {104-106},

abstract = {A comment on "Neurophysiological dynamics of phrase-structure building during sentence processing" by Nelson et al (2017), Proceedings of the National Academy of Sciences USA 114(18), E3669-E3678.},

keywords = {word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2013f,

title = {The placement of the head that maximizes predictability. An information theoretic approach},

author = {R. Ferrer-i-Cancho},

url = {Ihttp://hdl.handle.net/2117/108830},

year  = {2017},

date = {2017-01-01},

journal = {Glottometrics},

volume = {39},

pages = {38-71},

abstract = {The minimization of the length of syntactic dependencies is a well-established principle of word order and the basis of a mathematical theory of word order. Here we complete that theory from the perspective of information theory, adding a competing word order principle: the maximization of predictability of a target element. These two principles are in conflict: to maximize the predictability of the head, the head should appear last, which maximizes the costs with respect to dependency length minimization. The implications of such a broad theoretical framework to understand the optimality, diversity and evolution of the six possible orderings of subject, object and verb, are reviewed.},

keywords = {information theory, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Gomez2016a,

title = {Scarcity of crossing dependencies: a direct outcome of a specific constraint?},

author = {C. Gómez-Rodríguez and R. Ferrer-i-Cancho},

doi = {10.1103/PhysRevE.96.062304},

year  = {2017},

date = {2017-01-01},

journal = {Physical Review E},

volume = {96},

pages = {062304},

abstract = {The structure of a sentence can be represented as a network where vertices are words and edges indicate syntactic dependencies. Interestingly, crossing syntactic dependencies have been observed to be infrequent in human languages. This leads to the question of whether the scarcity of crossings in languages arises from an independent and specific constraint on crossings. We provide statistical evidence suggesting that this is not the case, as the proportion of dependency crossings of sentences from a wide range of languages can be accurately estimated by a simple predictor based on a null hypothesis on the local probability that two dependencies cross given their lengths. The relative error of this predictor never exceeds 5% on average, whereas the error of a baseline predictor assuming a random ordering of the words of a sentence is at least six times greater. Our results suggest that the low frequency of crossings in natural languages is neither originated by hidden knowledge of language nor by the undesirability of crossings per se, but as a mere side effect of the principle of dependency length minimization.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2013d,

title = {Random crossings in dependency trees},

author = {R. Ferrer-i-Cancho},

url = {http://hdl.handle.net/2117/106079},

year  = {2017},

date = {2017-01-01},

journal = {Glottometrics},

volume = {37},

pages = {1-12},

abstract = {It has been hypothesized that the rather small number of crossings in real syntactic dependency trees is a side-effect of pressure for dependency length minimization. Here we answer a related important research question: what would be the expected number of crossings if the natural order of a sentence was lost and replaced by a random ordering? We show that this number depends only on the number of vertices of the dependency tree (the sentence length) and the second moment about zero of vertex degrees. The expected number of crossings is minimum for a star tree (crossings are impossible) and maximum for a linear tree (the number of crossings is of the order of the square of the sequence length).},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2016a,

title = {Liberating language research from dogmas of the 20th century.},

author = {R. Ferrer-i-Cancho and C. Gómez-Rodríguez},

url = {http://hdl.handle.net/2117/85273},

year  = {2016},

date = {2016-01-01},

journal = {Glottometrics},

volume = {33},

pages = {33-34},

abstract = {A commentary on the article "Large-scale evidence of dependency length minimization in 37 languages" by Futrell, Mahowald & Gibson (PNAS 2015 112 (33) 10336-10341).},

keywords = {word order},

pubstate = {published},

tppubtype = {article}

}

@article{Kershenbaum2016a,

title = {Acoustic sequences in non-human animals: a tutorial review and prospectus},

author = {Arik Kershenbaum and Daniel T. Blumstein and Marie A. Roch and Çağlar Akçay and Gregory Backus and Mark A. Bee and Kirsten Bohn and Yan Cao and Gerald Carter and Cristiane Cäsar and Michael Coen and Stacy L. DeRuiter and Laurance Doyle and Shimon Edelman and Ramon Ferrer-i-Cancho and Todd M. Freeberg and Ellen C. Garland and Morgan Gustison and Heidi E. Harley and Chloé Huetz and Melissa Hughes and Julia Hyland Bruno and Amiyaal Ilany and Dezhe Z. Jin and Michael Johnson and Chenghui Ju and Jeremy Karnowski and Bernard Lohr and Marta B. Manser and Brenda McCowan and Eduardo Mercado and Peter M. Narins and Alex Piel and Megan Rice and Roberta Salmi and Kazutoshi Sasahara and Laela Sayigh and Yu Shiu and Charles Taylor and Edgar E. Vallejo and Sara Waller and Veronica Zamora-Gutierrez},

doi = {10.1111/brv.12160},

year  = {2016},

date = {2016-01-01},

journal = {Biological Reviews},

volume = {91},

number = {1},

pages = {13–52},

abstract = {Animal acoustic communication often takes the form of complex sequences, made up of multiple distinct acoustic units. Apart from the well‐known example of birdsong, other animals such as insects, amphibians, and mammals (including bats, rodents, primates, and cetaceans) also generate complex acoustic sequences. Occasionally, such as with birdsong, the adaptive role of these sequences seems clear (e.g. mate attraction and territorial defence). More often however, researchers have only begun to characterise – let alone understand – the significance and meaning of acoustic sequences. Hypotheses abound, but there is little agreement as to how sequences should be defined and analysed. Our review aims to outline suitable methods for testing these hypotheses, and to describe the major limitations to our current and near‐future knowledge on questions of acoustic sequences. This review and prospectus is the result of a collaborative effort between 43 scientists from the fields of animal behaviour, ecology and evolution, signal processing, machine learning, quantitative linguistics, and information theory, who gathered for a 2013 workshop entitled, ‘Analysing vocal sequences in animals’. Our goal is to present not just a review of the state of the art, but to propose a methodological framework that summarises what we suggest are the best practices for research in this field, across taxa and across disciplines. We also provide a tutorial‐style introduction to some of the most promising algorithmic approaches for analysing sequences. We divide our review into three sections: identifying the distinct units of an acoustic sequence, describing the different ways that information can be contained within a sequence, and analysing the structure of that sequence. Each of these sections is further subdivided to address the key questions and approaches in that area. We propose a uniform, systematic, and comprehensive approach to studying sequences, with the goal of clarifying research terms used in different fields, and facilitating collaboration and comparative studies. Allowing greater interdisciplinary collaboration will facilitate the investigation of many important questions in the evolution of communication and sociality.},

keywords = {word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2014e,

title = {Reply to the commentary ``Be careful when assuming the obvious'', by P. Alday},

author = {R. Ferrer-i-Cancho},

doi = {10.1163/22105832-00501009},

year  = {2015},

date = {2015-01-01},

journal = {Language Dynamics and Change},

volume = {5},

number = {1},

pages = {147-155},

keywords = {word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2013e,

title = {The placement of the head that minimizes online memory. A complex systems approach},

author = {R. Ferrer-i-Cancho},

doi = {10.1163/22105832-00501007},

year  = {2015},

date = {2015-01-01},

journal = {Language Dynamics and Change},

volume = {5},

number = {1},

pages = {114-137},

abstract = {It is well known that the length of a syntactic dependency determines its online memory cost. Thus, the problem of the placement of a head and its dependents (complements or modifiers) that minimizes online memory is equivalent to the problem of the minimum linear arrangement of a star tree. However, how that length is translated into cognitive cost is not known. This study shows that the online memory cost is minimized when the head is placed at the center, regardless of the function that transforms length into cost, provided only that this function is strictly monotonically increasing. Online memory defines a quasi-convex adaptive landscape with a single central minimum if the number of elements is odd and two central minima if that number is even. We discuss various aspects of the dynamics of word order of subject (S), verb (V) and object (O) from a complex systems perspective and suggest that word orders tend to evolve by swapping adjacent constituents from an initial or early SOV configuration that is attracted towards a central word order by online memory minimization. We also suggest that the stability of SVO is due to at least two factors, the quasi-convex shape of the adaptive landscape in the online memory dimension and online memory adaptations that avoid regression to SOV. Although OVS is also optimal for placing the verb at the center, its low frequency is explained by its long distance to the seminal SOV in the permutation space.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2015c,

title = {Crossings as a side effect of dependency lengths},

author = {R. Ferrer-i-Cancho and C. Gómez-Rodríguez},

doi = {10.1002/cplx.21810},

year  = {2015},

date = {2015-01-01},

journal = {Complexity},

volume = {21},

pages = {320-328},

abstract = {The syntactic structure of sentences exhibits a striking regularity: dependencies tend to not cross when drawn above the sentence. We investigate two competing explanations. The traditional hypothesis is that this trend arises from an independent principle of syntax that reduces crossings practically to zero. An alternative to this view is the hypothesis that crossings are a side effect of dependency lengths, that is, sentences with shorter dependency lengths should tend to have fewer crossings. We are able to reject the traditional view in the majority of languages considered. The alternative hypothesis can lead to a more parsimonious theory of language.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2014c,

title = {A stronger null hypothesis for crossing dependencies},

author = {R. Ferrer-i-Cancho},

doi = {10.1209/0295-5075/108/58003},

year  = {2014},

date = {2014-01-01},

journal = {Europhysics Letters},

volume = {108},

number = {5},

pages = {58003},

abstract = {The syntactic structure of a sentence can be modeled as a tree where vertices are words and edges indicate syntactic dependencies between words. It is well known that those edges normally do not cross when drawn over the sentence. Here a new null hypothesis for the number of edge crossings of a sentence is presented. That null hypothesis takes into account the length of the pair of edges that may cross and predicts the relative number of crossings in random trees with a small error, suggesting that a ban of crossings or a principle of minimization of crossings are not needed in general to explain the origins of non-crossing dependencies. Our work paves the way for more powerful null hypotheses to investigate the origins of non-crossing dependencies in Nature.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2013c,

title = {The risks of mixing dependency lengths from sequences of different length},

author = {R. Ferrer-i-Cancho and H. Liu},

doi = {10.1515/glot-2014-0014},

year  = {2014},

date = {2014-01-01},

journal = {Glottotheory},

volume = {5},

number = {2},

pages = {143-155},

abstract = {Mixing dependency lengths from sequences of different length is a common practice in language research. However, the empirical distribution of dependency lengths of sentences of the same length differs from that of sentences of varying length. The distribution of dependency lengths depends on sentence length for real sentences and also under the null hypothesis that dependencies connect vertices located in random positions of the sequence. This suggests that certain results, such as the distribution of syntactic dependency lengths mixing dependencies from sentences of varying length, could be a mere consequence of that mixing. Furthermore, differences in the global averages of dependency length (mixing lengths from sentences of varying length) for two different languages do not simply imply a priori that one language optimizes dependency lengths better than the other because those differences could be due to differences in the distribution of sentence lengths and other factors.},

keywords = {word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2017c,

title = {Towards a theory of word order. Comment on "Dependency distance: A new perspective on syntactic patterns in natural language" by Haitao Liu et al.},

author = {R. Ferrer-i-Cancho},

doi = {10.1016/j.plrev.2017.06.019},

year  = {2014},

date = {2014-01-01},

journal = {Physics of Life Reviews},

volume = {21},

pages = {218-220},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2008e,

title = {Some word order biases from limited brain resources. A mathematical approach},

author = {R. Ferrer-i-Cancho},

doi = {10.1142/S0219525908001702},

year  = {2008},

date = {2008-01-01},

journal = {Advances in Complex Systems},

volume = {11},

number = {3},

pages = {393-414},

abstract = {In this paper, we propose a mathematical framework for studying word order optimization. The framework relies on the well-known positive correlation between cognitive cost and the Euclidean distance between the elements (e.g. words) involved in a syntactic link. We study the conditions under which a certain word order is more economical than an alternative word order by proposing a mathematical approach. We apply our methodology to two different cases: (a) the ordering of subject (S), verb (V) and object (O), and (b) the covering of a root word by a syntactic link. For the former, we find that SVO and its symmetric, OVS, are more economical than OVS, SOV, VOS and VSO at least 2/3 of the time. For the latter, we find that uncovering the root word is more economical than covering it at least 1/2 of the time. With the help of our framework, one can explain some Greenbergian universals. Our findings provide further theoretical support for the hypothesis that the limited resources of the brain introduce biases toward certain word orders. Our theoretical findings could inspire or illuminate future psycholinguistics or corpus linguistics studies.},

keywords = {word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2008f,

title = {Some limits of standard linguistic typology. The case of Cysouw's models for the frequencies of the six possible orderings of S, V and O},

author = {R. Ferrer-i-Cancho},

doi = {10.1142/S0219525908001702},

year  = {2008},

date = {2008-01-01},

journal = {Advances in Complex Systems},

volume = {11},

number = {3},

pages = {421-432},

abstract = {This article is a critical analysis of Michael Cysouw's comment "Linear Order as a Predictor of Word Order Regularities."},

keywords = {word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2006d,

title = {Why do syntactic links not cross?},

author = {R. Ferrer-i-Cancho},

doi = {10.1209/epl/i2006-10406-0},

year  = {2006},

date = {2006-01-01},

journal = {Europhysics Letters},

volume = {76},

number = {6},

pages = {1228-1235},

abstract = {Here we study the arrangement of vertices of trees in a 1-dimensional Euclidean space when the Euclidean distance between linked vertices is minimized. We conclude that links are unlikely to cross when drawn over the vertex sequence. This finding suggests that the uncommonness of crossings in the trees specifying the syntactic structure of sentences could be a side-effect of minimizing the Euclidean distance between syntactically related words. As far as we know, nobody has provided a successful explanation of such a surprisingly universal feature of languages that was discovered in the 60s of the past century by Hays and Lecerf. On the one hand, support for the role of distance minimization in avoiding edge crossings comes from statistical studies showing that the Euclidean distance between syntactically linked words of real sentences is minimized or constrained to a small value. On the other hand, that distance is considered a measure of the cost of syntactic relationships in various frameworks. By cost, we mean the amount of computational resources needed by the brain. The absence of crossings in syntactic trees may be universal just because all human brains have limited resources.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}

@article{Ferrer2004b,

title = {Euclidean distance between syntactically linked words},

author = {R. Ferrer-i-Cancho},

doi = {10.1103/PhysRevE.70.056135},

year  = {2004},

date = {2004-01-01},

journal = {Physical Review E},

volume = {70},

pages = {056135},

abstract = {We study the Euclidean distance between syntactically linked words in sentences. The average distance is significantly small and is a very slowly growing function of sentence length. We consider two nonexcluding hypotheses: (a) the average distance is minimized and (b) the average distance is constrained. Support for (a) comes from the significantly small average distance real sentences achieve. The strength of the minimization hypothesis decreases with the length of the sentence. Support for (b) comes from the very slow growth of the average distance versus sentence length. Furthermore, (b) predicts, under ideal conditions, an exponential distribution of the distance between linked words, a trend that can be identified in real sentences.},

keywords = {network science, word order},

pubstate = {published},

tppubtype = {article}

}