A stronger null hypothesis for crossing dependencies
Complexity & Quantitative Linguistics Lab LARCA Research Group, Departament de Ciències de la Computació, Universitat Politècnica de Catalunya, Campus Nord - Edifici Omega Jordi Girona Salgado 1-3, 08034 Barcelona, Catalonia, Spain
Received: 20 June 2014
Accepted: 10 November 2014
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.
PACS: 89.75.Hc – Networks and genealogical trees / 89.75.Fb – Structures and organization in complex systems / 05.40.Fb – Random walks and Levy flights
© EPLA, 2014