Language Evolution and Computation Bibliography

The naming game (NG) describes the agreement dynamics of a population of N agents interacting locally in pairs leading to the emergence of a shared vocabulary. This model has its relevance in the novel fields of semiotic dynamics and specifically to opinion formation and language evolution. The application of this model ranges from wireless sensor networks as spreading algorithms, leader election algorithms to user-based social tagging systems. In this paper, we introduce the concept of overhearing (i.e., at every time step of the game, a random set of N? individuals are chosen from the population who overhear the transmitted word from the speaker and accordingly reshape their inventories). When ? = 0 one recovers the behavior of the original NG. As one increases ?, the population of agents reaches a faster agreement with a significantly low-memory requirement. The convergence time to reach global consensus scales as logN as ? approaches 1.

In this study, the complex-network approaches are employed to investigate the word form networks and the lemma networks extracted from dependency syntactic treebanks of fifteen different languages. The results show that it is possible to classify human languages by means of the main parameters of complex networks. The complex-network approaches can obtain language classifications as precise as achieved by contemporary word order typology. Clustering experiments point to the fact that the difference between the word form networks and the lemma networks can make for a better classification of languages. In short, the dependency syntactic networks can reflect morphological variation degrees and morphological complexity.

That almost all language networks are small-world and scale-free raises the question of whether syntax plays a role to measure the complexity of a language network. To answer this question, we built up two random language (dependency) networks based on a dependency syntactic network and investigated the complexity of these three language networks to see if the non-syntactic ones have network indicators similar to the syntactic one. The results show that all the three networks are small-world and scale-free. While syntax influences the indicators of a complex network, scale-free is only a necessary but not sufficient condition to judge whether a network is syntactic or non-syntactic. The network analysis focuses on the global organization of a language, it may not reflect the subtle syntactic differences of the sentence structure.

In this paper we analyze the effect of a non-trivial topology on the dynamics of the so-called Naming Game, a recently introduced model which addresses the issue of how shared conventions emerge spontaneously in a population of agents. We consider in particular the small-world topology and study the convergence towards the global agreement as a function of the population size $N$ as well as of the parameter $p$ which sets the rate of rewiring leading to the small-world network. As long as $p \gg 1/N$ there exists a crossover time scaling as $N/p^2$ which separates an early one-dimensional-like dynamics from a late stage mean-field-like behavior. At the beginning of the process, the local quasi one-dimensional topology induces a coarsening dynamics which allows for a minimization of the cognitive effort (memory) required to the agents. In the late stages, on the other hand, the mean-field like topology leads to a speed up of the convergence process with respect to the one-dimensional case.

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.

We analyze the time evolution of a system of two coexisting languages (Castillian Spanish and Galician, both spoken in northwest Spain) in the framework of a model given by Abrams and Strogatz [Nature 424, 900 (2003)]. It is shown that, contrary to the model's initial prediction, a stable bilingual situation is possible if the languages in competition are similar enough. Similarity is described with a simple parameter, whose value can be estimated from fits of the data.