Language Evolution and Computation Bibliography

Much of the current debate about the development of modern language from protolanguage focuses on whether the process was primarily synthetic or analytic. I investigate attested mech- anisms of language change and emphasise the uncertainty inherent in the inferential nature of communication. Both synthesis and analysis are involved in the complexification of language, but the most significant pressure is the need for meanings to be reconstructible from context.

The Mirror System Hypothesis (MSH) of the evolution of brain mechanisms supporting language distinguishes a monkey-like mirror neuron system from a chimpanzee-like mirror system that supports simple imitation and a human-like mirror system that supports complex imitation and language. This paper briefly reviews the seven evolutionary stages posited by MSH and then focuses on the early stages which precede but are claimed to ground language. It introduces MNS2, a new model of action recognition learning by mirror neurons of the macaque brain to address data on audio-visual mirror neurons. In addition, the paper offers an explicit hypothesis on how to embed a macaque-like mirror system in a larger human-like circuit which has the capacity for imitation by both direct and indirect routes. Implications for the study of speech are briefly noted.

Semiotic dynamics is a fast growing field according to which language can be seen as an evolving and self-organizing system. In this paper we present a simple multi-agent framework able to account for the emergence of shared conventions in a population. Agents perform pairwise games and final consensus is reached without any outside control nor any global knowledge of the system. In particular we discuss how embedding the population in a non trivial interaction topology affects the behavior of the system and forces to carefully consider agents selection strategies. These results cast an interesting framework to address and study more complex issues in semiotic dynamics.

I discuss the ubiquity of power law distributions in language organisation (and elsewhere), and argue against Miller's (2000) argument that large vocabulary size is a consequence of sexual selection. Instead I argue that power law distributions are evidence that languages are best modelled as dynamical systems but raise some issues for models of iterated language learning.

In this paper, we present an agent-based simulation model for the evolution of language. This is based on a previous model proposed by the authors and inspired by Nowak's simplest mathematical model. We extend our previous work with the introduction of a significant characteristic: a world where the languages live and evolve, and which influences interactions among individuals. The main goal of this research is to present a model which shows how the presence of a topological structure influences the communication among individuals and contributes to the emergence of clusters of different languages.

Human languages are characterized by a number of universal patterns of structure and use. Theories differ on whether such linguistic universals are best understood as arbitrary features of an innate language acquisition device or functional features deriving from cognitive and communicative constraints. From the viewpoint of language evolution, it is important to explain how such features may have originated. We use computational simulations to investigate the circumstances under which universal linguistic constraints might get genetically fixed in a population of language learning agents. Specifically, we focus on the Baldwin effect as an evolutionary mechanism by which previously learned linguistic features might become innate through natural selection across many generations of language learners. The results indicate that under assumptions of linguistic change, only functional, but not arbitrary, features of language can become genetically fixed.

Compositionality is a hallmark of human language - words and morphemes can be factorially combined to produce a seemingly limitless number of viable strings. This contrasts with nonhuman communication systems, which for the most part are holistic - encoding a whole message through a single, gestalt form. Why does every human language adopt a compositional strategy? In this paper, we show that compositional language can arise automatically through grounded communication among populations of communicators. The proposed mechanism is the following: if a holistic and a compositional approach are in competition and if both structured (compositional) and atomic meanings need to be communicated, the holistic strategy becomes less successful as it does not recruit already acquired bits of language. We demonstrate the viability of this explanation through computer simulations in which populations of artificial agents perform a communicative task - describing scenes that they have observed. Successful language strategies (that is, those yielding successful transmission of information about a scene) are reinforced while unsuccessful ones are demoted. The simulations show that this reinforcement on the basis of communicative success indeed leads to the dominance of compositional language as long as the fraction of unstructured meaning to be communicated is sufficiently high. Moreover, following Elman (1993), we then show that the same effect can be achieved by, instead of manipulating the world (the fraction of unstructured meaning presented to the agents), letting the agents themselves go through developmental stages. These simulations confirm that simple reinforcement mechanisms applied during communicative interactions can account for the emergence of linguistic compositionality.

The Recent Out-of-Africa human evolutionary model seems to be generally accepted. This impression is very prevalent outside palaeoanthropological circles (including studies of language evolution), but proves to be unwarranted. This paper offers a short review of the main challenges facing ROA and concludes that alternative models based on the concept of metapopulation must be also considered. The implications of such a model for language evolution and diversity are briefly reviewed.

Most studies of vocalizations with chimpanzees and Bonobos focus on the interpretation of the vocal behaviour of both captive and free-ranging groups to relate sounds produced to their semantic contexts. Spectrographic analyses reveal the acoustic structure of the vocalizations but rarely raise the question of the specific articulatory capacities of Bonobos in relation to the acoustics. This point is essential if one wants to understand the articulatory control that Bonobos have on their vocalizations. It is also important when the vocalizations of Bonobos and the sound produced by modern humans are compared.

The systematic and universal communicative behaviour that drives human beings to give honest information to conspecifics during long-lasting conversational episodes still represents a Darwinian paradox. Attempts to solve it by comparing conversation with a mere reciprocal cooperative information exchange is at odds with the reality of spontaneous language use. The Costly Signalling Theory has recently attracted attention as a tentative explanation of the evolutionary stability of language. Unfortunately, it makes the wrong prediction that only elite individuals would talk. I show that as far as social bonding is assortative in our species, generalised signalling through language becomes a viable strategy to attract allies.

Is the range of languages we observe today explainable in terms of which languages can be learned easily and which cannot? If so, the key to understanding language is to understand innate learning biases, and the process of biological evolution through which they have evolved. Using mathematical and computer modelling, we show how a very small bias towards regularity can be accentuated by the process of cultural transmission in which language is passed from generation to generation, resulting in languages that are overwhelmingly regular. Cultural evolution therefore plays as big a role as prior bias in determining the form of emergent languages, showing that language can only be explained in terms of the interaction of biological evolution, individual development, and cultural transmission.

Isolating-Monocategorial-Associational (IMA) Language is language with the following three properties: (a) morphologically isolating, without word-internal morphological structure; (b) syntactically monocategorial, without distinct syntactic categories; and (c) semantically associational, without distinct construction-specific semantic rules, compositional semantics relying instead on the association operator, which says that the meaning of a composite expression is associated with the meanings of its constituents in an underspecified fashion. IMA Language is present in the following five domains: (a) phylogeny: at some stage in evolution, early language was IMA Language; (b) ontogeny: at some stage in acquisition, early child language is IMA Language; (c) semiotics: some artificial languages are IMA Language; (d) typology: some languages are closer than others to IMA Language; and (e) cognition: IMA Language is a feature of general human cognition. This paper presents arguments pertaining to the first of these domains, namely phylogeny, citing evidence from the linguistic behaviour of captive apes which points towards the conclusion that early human language was IMA Language.

Compositionality and regularity are universals in human languages; in most languages, complex expressions are determined by their structures and their components' meanings. Based on a multi-agent computational model, the coevolution of compositionality and one type of regularity, word order, is traced during the emergence of compositional language out of holistic signals. The model modifies some questionable aspects in the Iterated Learning Model and Fluid Construction Grammar by considering the conventionalization in horizontal transmission and the gradual formation of syntactic categories which mirror the semantic categories. The model also implements a bottom-up syntactic developmental process, i.e., the global orders for regulating multiple arguments are gradually formed from simple local orders between two categories.

Although Hauser, Chomsky and Fitch (HCF/FHC) and Pinker and Jackendoff (PJ/JP) differ in the epistemic questions they ask concerning, respectively, the nature of language (what language is), and the evolution of language (what language evolved for), it will be argued that both questions are part of the same methodological framework. This framework resembles the classical manner in which scientific knowledge is to be obtained while newer epistemological methods are suggested that can complement the study of the characteristics of language and evolutionary transitions that led to language.

I describe and assess the Minimalist Program (MP) as an approach to the evolution of language. The MP is less about evolution than explanation, but if its attempt to vindicate a certain idea of 'design perfection' was successful, a deeper level of explanation would be achieved than historical narrative and functional explanation affords, and the evolution problem would be solved along the way. Arguably, a minimalist methodology is also a necessary component in any explanatory approach to language evolution, no matter its theoretical orientation. While these are clear virtues, I question the MP's central explanatory claim, that language can be understood as an optimal solution to the problem of satisfying interface conditions imposed by pre-linguistic cognitive systems.

Ambiguity is a defining property of natural language distinguishing it from artificial languages. It would seem to be dysfunctional, and therefore its ubiquity in language poses an evolutionary puzzle. This paper discusses the implications of a typical iterated learning model on the conditions under which syntactic ambiguity emerges and stabilises in language. It contrasts the purely nativist stance that language imperfections such as syntactic ambiguity are artifacts arising from internal constraints of the genetically determined language faculty with the view that they are frozen accidents persisting because they are easily learnt.

Before the evolution of languages as public conventional communication systems, pre-humans had somewhat complex private mental schemes for representing the external world. What is known about human and some animal vision suggests that proposition-like cognitive structures existed for the mental representation of perceived scenes before the advent of complex language. The structures traditionally adopted by formal Logic can be modified to conform to known constraints on the visual representation of scenes. While this modification slightly reduces the expressive power of representations (in that the meanings of some complex sentences cannot naturally be represented), it provides a unified, ontologically parsimonious, primitive notation for cognitive representations, suitable for later recruitment by complex syntactic language. The most basic semantic elements later mapped onto sentences are all present in the prelinguistic mental representation, which reflects the workings of the visual attention system

ChickenHawk is a social-dilemma game in which the only way to win is to play ''Hawk'' against ''Chicken.'' The purpose of the game is to distinguish between uncoordinated and coordinated self-sacrifice. In a test of four signaling conditions with players who belong to a culturally homogeneous population, a 'cheap talk' condition led to efficient coordination, whereas signaling opportunities engaging social reputation and allowing eye-contact without speech yielded poorly coordinated altruistic behavior. The implications are: (1) without language, mere willingness to cooperate on a social dilemma is insufficient for coordinating intentions, and (2) given a sufficiently cohesive social group, language can coordinate inequitable, altruistic sacrifices of modest but real material incentives, even where fully anonymous defection is an option.

The possibilities for a stepwise evolution of grammar are evaluated through an analysis of which components of modern human grammar are removable, and in what order, while still leaving a functional communication system. It is found that recursivity is a prime candidate for being a late evolutionary addition, with flexibility and hierarchical rules coming next. Furthermore, it is argued that recursivity need not be the unitary infinite-loop concept of formal grammars, but can evolve in several smaller steps.

The precise timing of the emergence of language in human prehistory cannot be resolved. But the available evidence is sufficient to constrain it to some degree. This is a review and synthesis of the available evidence, leading to the conclusion that the time when speech became important for our ancestors can be constrained to be not less than 500,000 years ago, thus excluding several popular theories involving a late transition to speech.

Many scholars assume a connection between the evolution of language and that of distinctively human group-level morality. Unfortunately, such thinkers frequently downplay a central implication of modern Darwinian theory, which precludes the possibility of innate psychological mechanisms evolving to benefit the group at the expense of the individual. Group level moral regulation is indeed central to sexual, social and political life in all known hunter-gatherer communities. The production of speech acts would be impossible without such regulation. The challenge, therefore, is to explain on a Darwinian basis how life could have become subject to the rule of law. Only then will we have an appropriate social framework in which to contextualize our models of how language may have evolved.

Synthetic and holistic theories of protolanguage are typically seen as being in opposition. In this paper I 1) evaluate a recent critique of holistic protolanguage 2) sketch how the differences between these two theories can be reconciled, 3) consider a more fundamental problem with the concept of protolanguage.

The debate over the evolution of an innate language capacity seems to divide into two principle camps. The neo-Darwinian approach generally argues that human psychological modules, in- cluding the language faculty, must have arisen gradually and incrementally having been honed by natural selection. Thus Pinker, when theorizing about language evolution, sees ''no reason to doubt that the principle explanation is the same as for any other complex instinct or organ, Darwin's theory of natural selection'' (Pinker, 1994, 333). However, as Knight et al. (2000) have pointed out, little attention has been paid by the neo-Darwinian approach to address the causes of the emergence of novelty. The saltationist approach gleans much of its evidence from the archaeological and paleontological record, which is interpreted as unsupportive of the neo-Darwinian paradigm. Jackendoff (1999) accuses those who do not accept that language arose gradually through natural selection as having been ''forced to devalue evolutionary argu- mentation''. Jackendoff's concern seems to stem from the view that there is only one way that evolution can proceed, through gradual change driven by natural selection. My concern is for the neglect of the vast amount of evidence supporting the theory that modern humans did not emerged in a gradual, step-wise fashion, so there is no reason to believe that cognition and lan- guage evolved in this manner. Here I argue that hominins evolved through major evolutionary leaps, which may have numbered only two or three significant mutation 'events'. Neoteny (the retention of infant or juvenile growth rates) appears to have been a major force in the evolu- tion of our primate ancestors and this process can explain the sudden emergence of many of the traits that define what it means to be human. Further evidence from the fossil and archaeological record supports a 'sudden' emergence of human cognition and language.

A major feature that sets language apart from other communication systems is the use of categorylabels -- words. In addition to providing a means of communication, there is growing evidence that category labels play a role in the formation and shaping of concepts. If verbal labels help humans acquire or use category information, one can ask whether it is easier to learn labeled categories compared to unlabeled ones. Normal English-speaking adults participated in a category-learning task in which categories were labeled or unlabeled. The presence of labels facilitated the learning of unfamiliar categories and resulted in more robust category representations. The advantage for acquiring named categories was observed even though the category labels did not convey any additional information and all participants had equivalent experience categorizing the stimuli. This work provides empirical support for the idea of labels as conceptual anchor points (Clark, 1997).

In this paper we will describe the results of an experiment in which an effective communication system arises among a collection of initially non-communicating agents through a self-organization process based on an evolutionary process. Evolved agents communicate by producing and detecting five different signals that affect both their motor and signaling behavior. These signals identify features of the environment and of the agents/agents and agents/environmental relations that are crucial for solving the given problem. The obtained results also indicate that individual and social/communicative behaviors are tightly co-adapted.

The majority of extant languages have one of three basic word orders: SVO, SOV or VSO. Various hypotheses have been put forward to explain aspects of this bias, including the existence of a universal grammar, learnability imposed by non-linguistic-specific cognitive constraints, and the descent of the extant languages from a common ancestral proto-language. Here, we adopt a multi-agent model for language emergence that simulates the coevolution of a lexicon and syntax from a holistic signaling system. The syntax evolves through a process of categorization; local syntactic rules are constructed that assign a relative order (e.g., S before V) to the elements of the two categories to which each rule applies. We demonstrate that local syntax encoding the relative position of S and O are the most stable, allowing the coexistence of the global word order pairs SOV/SVO and VOS/OVS. The structure of the semantic space that the language encodes further constrains the global syntax that is stable.

Selective pressures for the evolutionary emergence of human language tend to be interpreted as social in nature, i.e., for better social communication and coordination. Using a simple neural network model of language acquisition we demonstrate that even using language for oneself, i.e., as private or inner speech, improves an individual's categorization of the world and, therefore, makes the individual's behavior more adaptive. We conclude that language may have first emerged due to the advantages it confers on individual cognition, and not only for its social advantages.

In this paper, we present a model of language acquisition which can be used to explain how children learn a grammar by interacting with their surroundings. We build upon the model proposed by Komarova et al in the context of evolution of grammars. We test our model for two situations : One, in which an individual is trying to learn a grammar in an environment where everybody uses the same grammar, and the other in which different groups in the population use different grammars.

A recent proposal (Hauser, Chomsky \& Fitch, 2002) suggests that the crucial defining property of human language is recursion. In this paper, following a critical analysis of what is meant by the term, I examine three reasons why the recursion-only hypothesis cannot be correct: (i) recursion is neither unique to language in humans, nor unique to our species, (ii) human language consists of many properties which are unique to it, and independent of recursion, and (iii) recursion may not even be necessary to human communication. Consequently, if recursion is not the key defining property of human language, it should not be granted special status in an evolutionary account of the system.

In this paper we present a computational model for the emergence of a fixed word order in the language of a society of babbling agents. In contrast to the majority of research modeling the emergence of syntactic principles, in which a very strong governing role is set aside for the semantic aspect of communication, this paper touches on the possibility that one of the most basic grammatical principles, i.e. fixed word order, can develop without direct reference to concepts of shared meaning. With its rigid data-driven approach, the system described in this paper introduces a hitherto unexplored baseline perspective to the research efforts modeling the emergence of grammatical properties in language.

Many theories of language evolution assume a selection pressure for the communication of propositional content. However, if the content of such utterances is of value then information sharing is altruistic, in that it provides a benefit to others at possible expense to oneself. Close consideration of cross-disciplinary evidence suggests that speaking is in fact selfish, in that the speaker receives a direct payoff when successful communication takes place. This is congruent with the orthodox view of animal communication, and it is suggested that future research be conducted within this context.

Within a semiogenetic theory of the emergence and evolution of the language sign, I claim that a structural-notional analysis of submorphemic data provided by certain reconstructed PIE roots and their reflexes, projected as far back as theories of the evolution of speech will permit by a principle of articulatory invariance, points to the existence of an unconscious neurophysiologically grounded strategy for 'naming' parts of the body. Specifically, it is claimed that the occlusive sounds produced by open-close movements of the mouth, which have been shown experimentally to be synchronized with open-close movements of the hand(s), may have functioned as 'core invariants'. Morphogenetically transformed into conventionalized language signs, these could have served to 'name' not only the mouth movements and articulators involved, but also the hand movements with which they appear to be coordinated, as well as the hand itself.

In a study by Cavalli-Sforza et al. (1988), the spread of anatomically modern man was reconstructed on the basis of genetic and linguistic pieces of evidence: the main conclusion was that these two approaches reflect a common underlying history, the history of our past still frozen in the genes of modern populations. The expression `genetic history' was introduced (Piazza et al. 1988) to point out that if today we find many genes showing the same geographical patterns in terms of their frequencies, this may be due to the common history of our species. A deeper exploration of the whole problem can be found in Cavalli-Sforza et al. (1994). In the following, some specific cases of structural analogies between linguistic and genetic geographical patterns will be explored that supply further and more updated information. It is important to emphasize at the outset that evidence for coevolution of genes and languages in human populations does not suggest by itself that some genes of our species determine the way we speak; this coevolution may simply be due to a common mode of transmission and mutation of genetic and linguistic units of information and common constraints of demographic factors.

The majority of studies on animal communication provide evidence that gestural signaling plays an important role in the communication of nonhuman primates and resembles that of pre-linguistic and just-linguistic human infants in some important ways. However, ape gestures also differ from the gestures of human infants in some important ways as well, and these differences might provide crucial clues for answering the question of how human language -- at least in its cognitive and social-cognitive aspects- evolved from the gestural communication of our ape-like ancestors. The present manuscript summarizes and compares recent studies on the gestural signaling of the great apes (Gorilla gorilla, Pan paniscus, Pan troglodytes, Pongo pygmaeus) to enable a comparison with gestures in children. We focused on the three following aspects: 1) nature of gestures, 2) intentional use of gestures, 3) and learning of gestures. Our results show, that apes have multifaceted gestural repertoires and use their gestures intentionally. Although some group-specific gestures seem to be acquired via a social learning process, the majority of gestures are learned via individual learning. Importantly, all of the intentional produced gestures share two important characteristics that make them crucially different from human deictic and symbolic gestures: 1) they are almost invariably used in dyadic contexts and 2) they are used exclusively for imperative purposes. Implications for these differences are discussed.

This paper argues that the evolution of human language is a prerequisite to the evolution of human morality. Human moral systems are not possible without fully complex language. Though protolanguage can extend moral systems, the design features of human language greatly extend human moral ability. Specifically, this paper focuses on how recursion, linguistic creativity, naming ability, displacement, and compositionality extend moral systems. The argument descriptively defines altruism as self-sacrificial behavior for others and morality as how a group classifies right and wrong behavior. No comment is made on how altruism squares with the replicatory selfishness of genes, or on the controversy of group selection. However, along with Dawkins (Dawkins, 1976), the author concurs that humans can use linguistically based concepts to help constrain genetic selfishness and promote degrees of altruism and morality. Though drawing on previous research, the ideas presented here are novel to the extent that they demonstrate how the design features of language support and extend human altruism and morality.

Vocal learning is a key component of the human language faculty, and is a behaviour we share with only a few other species in nature. Perhaps the most studied example of this phenomenon is bird song which displays a number of striking parallels with human language, particularly in its development. In this paper we present a simple computational model of bird song development and then use this in a model of evolution to investigate some of the ecological conditions under which vocal behaviour can become more or less reliant on cultural transmission.

We present a framework and first set of simulations for evolving a language for communicating about space. The framework comprises two components: (1) An established mobile robot platform, RatSLAM, which has a 'brain' architecture based on rodent hippocampus with the ability to integrate visual and odometric cues to create internal maps of its environment. (2) A language learning system based on a neural network architecture that has been designed and implemented with the ability to evolve generalizable languages which can be learned by naive learners. A study using visual scenes and internal maps streamed from the simulated world of the robots to evolve languages is presented. This study investigated the structure of the evolved languages showing that with these inputs, expressive languages can effectively categorize the world. Ongoing studies are extending these investigations to evolve languages that use the full power of the robots representations in populations of agents.

Simultaneous acquisition of multiple languages to a native level of fluency is common in many areas of the world. This ability must be represented in any cognitive mechanisms used for language. Potential explanations of the evolution of language must also account for the bilingual case. Surprisingly, this fact has not been widely considered in the literature on language origins and evolution. We consider any array of potential accounts for this phenomenon, including arguments by selectionists on the basis for language variation. We find scant evidence for specific selection of the multilingual ability prior to language origins. Thus it seems more parsimonious that bilingualism ``came for free'' along with whatever mechanisms did evolve. Sequential learning mechanisms may be able to accomplish multilingual acquisition without specific adaptations. In support of this perspective, we present a simple recurrent network model that is capable of learning two idealized grammars simultaneously. These results are compared with recent studies of bilingual processing using eyetracking and fMRI showing vast overlap in the areas in the brain used in processing two different languages.

This paper describes evolutionary dynamics in language and presents a genetic framework of language akin to those of Croft (2000) and Mufwene (2001), where language is a complex system that inhabits, interacts with and evolves in communities of human speakers. The novelty of the present framework resides in the separation between form (phonology and syntax) and meaning (semantics), which are described as two different selection systems, connected by symbolic association and by probabilistic encoding of information.

We propose to address a series of questions related to the evolution of languages by statistical analysis of written text. We develop a ''statistical signature'' of a language, analogous to the genetic signature proposed by Karlin in biology, and we show its stability within languages and its discriminative power between languages. Using this representation, we address the question of its trajectory during language evolution. We first reconstruct a phylogenetic tree of IE languages using this property, in this way showing that it also contains enough information to act as a ''tracking'' tag for a language during its evolution. One advantage of this kind of phylogenetic trees is that they do not depend on any semantic assessment or on any choice of words. We use the ''statistical signature'' to analyze a time-series of documents from four romance languages, following their transition from latin. The languages are italian, french, spanish and portuguese, and the time points correspond to all centuries from III bC to XX AD.

An evolutionary perspective on signaling games is adopted to explain some semantic universals concerning truth-conditional connectives; property denoting expressions, and generalized quantifiers. The question to be addressed is: of the many meanings of a particular type that can be expressed, why are only some of them expressed in natural languages by `simple' expressions

This paper investigates the effect overextensions of words may have on the emergence of compositional structures in language. The study is done using a recently developed computer model that integrates the iterated learning model with the language game model. Experiments show that overextensions due to an incremental acquisition of meanings on the one hand attracts languages into compositional structures, but on the other hand introduces ambiguities that may act as an antagonising pressure.

Grammaticalisation is relevant for language evolution in two ways. First, it is possible to model grammaticalisation processes by evolutionary simulations (iterated learning). This paper provides two such models of a central step in the grammaticalisation process: the recruitment of lexical and functional words for a new functional role. These models help in better understanding the processes involved. Second, it is possible to reason backwards to earlier stages of human language. The paper argues that all that is necessary for the genesis of natural languages is the conventionality of the form-meaning association and the possibility of introducing new lexical words. Once there is a communication system of this kind, all the additional complexities of human languages follow.

We present the rationale and ongoing research of an interdisciplinary international project aiming at developing a novel theory of semiotic development, on the basis of broad developmental, cross-species and cross-cultural research. We focus on five social- cognitive domains: (i) perception and categorization, (ii) iconcity and pictures, (iii) space and metaphor, (iv) imitation and mimesis and (v) intersubjectivity and conventions, each of which is briefly described. Our main hypothesis is that what distinguishes human beings from other animals is an advanced capacity to engage in sign use, which on its part allowed for the evolution of language.

In this paper, we investigate the combination of collaborative tagging and emergent semantics for improved data navigation and search. We propose to use visual features in addition to tags provided by users in order to discover new relationships between data. We show that our method is able to overcome some of the problems involved in navigating databases using tags only, such as synonymy or different languages, spelling mistakes, homonymy, or missing tags. On the other hand, image search based on visual features can be simplified substantially by the use of tags. We present technical details of our prototype system and show some preliminary results.

Semiotic dynamics is a novel field that studies how semiotic conventions spread and stabilize in a population of agents. This is a central issue both for theoretical and technological reasons since large system made up of communicating agents, like web communities or artificial embodied agents teams, are getting widespread. In this paper we discuss a recently introduced simple multi-agent model which is able to account for the emergence of a shared vocabulary in a population of agents. In particular we introduce a new deterministic agents' playing strategy that strongly improves the performance of the game in terms of faster convergence and reduced cognitive effort for the agents.

There is a growing body of research on multi-agent systems bootstrapping a communication system. Most studies are based on simulation, but recently there has been an increased interest in the properties and formal analysis of these systems. Although very interesting and promising results have been obtained in these studies, they always rely on major simplifications. For example, although much larger populations are considered than was the case in most earlier work, previous work assumes the possibility of meaning transfer. With meaning transfer, two agents always exactly know what they are talking about. This is hardly ever the case in actual communication systems, as noise corrupts the agents' perception and transfer of meaning. In this paper we first consider what happens when relaxing the meaning-transfer assumption, and propose a cross-situational learning scheme that allows a population of agents to still bootstrap a common lexicon under this condition. We empirically show the validity of the scheme and thereby improve on the results reported in (Smith, 2003) and (Vogt and Coumans, 2003) in which no satisfactory solution was found. It is not our aim to reduce the importance of previous work, instead we are excited by recent results and hope to stimulate further research by pointing towards some new challenges.

In this paper we present the results of an experiment in which a collection of simulated robots that are evolved for the ability to solve a collective navigation problem develop a communication system that allow them to better cooperate. The analysis of the obtained results indicates how evolving robots develop a non-trivial communication system and exploit different communication modalities.

In this article we present an evolutionary technique for developing a neural network based controller for an an- thropomorphic robotic arm with 4 DOF able to exhibit a reaching behaviour. Evolved neural controllers display an ability to reach targets accurately and generalize their ability to moving targets. This study demonstrates that it is possible to obtain solutions that are extremely parsimonious from the point of view of the control system. Evolutionary training techniques allow us to evolve parameters of the control system on the basis of the global effects that they produce on the dynamics arising from the interaction between the control system, the robot's body and the environment.

A set of simulations are presented that investigate generalization in languages evolved for mobile robots. The mobile robot platform is RatSLAM, a model for Simultaneous Localization and Mapping based on rodent hippocampus that uses visual and odometric information to build up a map of the explored environment. The language agents use information from this system as inputs and are based on simple recurrent neural networks. This paper describes two sets of experiments exploring the nature of generalization in evolved languages. The first study investigated languages evolved from visual inputs and the second study investigated languages evolved from position representations. These studies showed that processing the input prior to the language agent affects the expressivity of the languages and the performance of the agents. Some generalization occurs in these languages. Studies are ongoing to extend these simulations using the simulated world of the robots.

What purposes, other than facilitating the sharing of information, can language have served? First, it may not have evolved to serve any purpose at all. It is possible that language is just a side effect of the large human brain—a spandrel or exaptation—that only became useful ...

The emergence of language in populations of primates that initially lacked language can be simulated with artificial organisms controlled by neural networks and living, evolving, and learning in artificial environment. Some simulations have already been done but most are a task for the future. We dis-cuss language evolution under two topics: language is learned from others on the basis of genetically inherited predispositions, and language has important influences on human cognition. We propose an evolutionary sequence accord-ing to which bipedalism and the emergence of the hands represent a selective pressure for developing an ability to predict the consequences of one's actions, this ability is the basis for learning by imitating other individuals, learning by imitating other individuals is applied to learning to imitate their communicative behaviour. The second topic include the consequences of language for various aspects of human cognition, especially when language is used to talk to oneself.

Neural networks have been proposed as an ideal cognitive modeling methodology to deal with the symbol grounding problem. More recently, such neural network approaches have been incorporated in studies based on cognitive agents and robots. In this paper we present a new model of symbol grounding transfer in cognitive robots. Language learning simulations demonstrate that robots are able to acquire new action concepts via linguistic instructions. This is achieved by autonomously transferring the grounding from directly grounded action names to new higher-order composite actions. The robot's neural network controller permits such a grounding transfer. The implications for such a modeling approach in cognitive science and autonomous robotics are discussed.

Cross-linguistic similarities are reflected by the speech sound systems of languages all over the world. In this work we try to model such similarities observed in the consonant inventories, through a complex bipartite network. We present a systematic study of some of the appealing features of these inventories with the help of the bipartite network. An important observation is that the occurrence of consonants follows a two regime power law distribution. We find that the consonant inventory size distribution together with the principle of preferential attachment are the main reasons behind the emergence of such a two regime behavior. In order to further support our explanation we present a synthesis model for this network based on the general theory of preferential attachment.

In this paper we introduce a model for the simulation of language evolution, which is incorporated in the New Ties project. The New Ties project aims at evolving a cultural society by integrating evolutionary, individual and social learning in large scale multi-agent simulations. The model presented here introduces a novel implementation of language games, which allows agents to communicate in a more natural way than with most other existing implementations of language games. In particular, we propose a hybrid mechanism that combines cross-situational learning techniques with more informed feedback mechanisms. In our study we focus our attention on dealing with referential indeterminacy after joint attention has been established and on whether the current model can deal with larger populations than previous studies involving cross-situational learning. Simulations show that the proposed model can indeed lead to coherent languages in a quasi realistic world environment with larger populations.

We start by providing an evolutionary scenario for the emergence of semantics. It is argued that the evolution of anticipatory cognition and theory of mind in the hominids opened up for cooperation about future goals. This cooperation requires symbolic communication. The meanings of the symbols are established via a ``meeting of minds.'' The concepts in the minds of communicating individuals are modelled as convex regions in conceptual spaces. We then outline a mathematical framework based on fixpoints in continuous mappings between conceptual spaces that can be used to model such a semantics.

This paper describes a machine learning method that enables robots to learn the capability of linguistic communication from scratch through verbal and nonverbal interaction with users. The method focuses on two major problems that should be pursued to realize natural human-machine conversation: a scalable grounded symbol system and belief sharing. The learning is performed in the process of joint perception and joint action with a user. The method enables the robot to learn beliefs for communication by combining speech, visual, and behavioral reinforcement information in a probabilistic framework. The beliefs learned include speech units like phonemes or syllables, a lexicon, grammar, and pragmatic knowledge, and they are integrated in a system represented by a dynamical graphical model. The method also enables the user and the robot to infer the state of each other's beliefs related to communication. To facilitate such inference, the belief system held by the robot possesses a structure that represents the assumption of shared beliefs and allows for fast and robust adaptation of it through communication with the user. This adaptive behavior of the belief systems is modeled by the structural coupling of the belief systems held by the robot and the user, and it is performed through incremental online optimization in the process of interaction. Experimental results reveal that through a practical, small number of learning episodes with a user, the robot was eventually able to understand even fragmental and ambiguous utterances, act upon them, and generate utterances appropriate for the given situation. This work discusses the importance of properly handling the risk of being misunderstood in order to facilitate mutual understanding and to keep the coupling effective.

We present a mathematical model of cross-situational learning, in which we quantify the learnability of words and vocabularies. We find that high levels of uncertainty are not an impediment to learning single words or whole vocabulary systems, as long as the level of uncertainty is somewhat lower than the total number of meanings in the system. We further note that even large vocabularies are learnable through cross-situational learning.

Children learn language from what they hear. In dispute is what mechanisms they bring to this task. Clearly some of these mechanisms have evolved to support the human speech capacity but this leaves a wide field of possibilities open. The question I will address in my paper is whether we need to postulate an innate $\underline{syntactic}$ module that has evolved to make the learning of language structure possible. I will suggest that more general human social and cognitive capacities may be all that is needed to support the learning of syntactic structure.

In this article, we study the emergence of associations between words and concepts using the self-organizing map. In particular, we explore the meaning negotiations among communicating agents. The self-organizing map is used as a model of an agent's conceptual memory. The concepts are not explicitly given but they are learned by the agent in an unsupervised manner. Concepts are viewed as areas formed in a self-organizing map based on unsupervised learning. The language acquisition process is modeled in a population of simulated agents by using a series of language games, specifically observational games. The results of the simulation experiments verify that the agents learn to communicate successfully and a shared lexicon emerges. This work was supported by the Academy of Finland through Adaptive Informatics Research Centre that is a part of the Finnish Centre of Excellence Programme.

How does a shared lexicon arise in population of agents with differing lexicons, and how can this shared lexicon be maintained over multiple generations? In order to get some insight into these questions we present an ALife model in which the lexicon dynamics of populations that possess and lack metacommunicative interaction (MCI) capabilities are compared. We suggest that MCI serves as a key component in the maintenance of a linguistic interaction system. We ran a series of experiments on mono-generational and multi-generational populations whose initial state involved agents possessing distinct lexicons. These experiments reveal some clear differences in the lexicon dynamics of populations that acquire words solely by introspection contrasted with populations that learn using MCI or using a mixed strategy of introspection and MCI. Over a single generation the performance between the populations with and without MCI is comparable, in that the lexicon converges and is shared by the whole population. In multi-generational populations lexicon diverges at a faster rate for an introspective population, eventually consisting of one word being associated with every meaning, compared with MCI capable populations in which the lexicon is maintained, where every meaning is associated with a unique word.

The inflection of words based on agreement, such as number, gender and case, is considered to contribute to clarify the dependency between words in a sentence. Our purpose in this study is to investigate the efficiency of word inflections with HPSG (Head-driven Phrase Structure Grammar), which is able to deal with these features directly. Using a notion of utility, we measure the efficiency of a grammar in terms of the balance between the number of semantic structures of a sentence, and the cost of agreement according to the number of unification processes. In our experiments, we showed how these were balanced in two different corpora. One, WSJ (Wall Street Journal), includes long and complicated sentences, while the other corpus, ATIS (Air Travel Information System) does shorter colloquial sentences. In the both corpora, agreement is surely important to reduce ambiguity. However, the importance of agreement in the ATIS corpus became salient as personal pronouns were so often employed in it, compared with the WSJ corpus.

The Human Speechome Project is an effort to observe and computationally model the longitudinal course of language development for a single child at an unprecedented scale. We are collecting audio and video recordings for the first three years of one child's life, in its near entirety, as it unfolds in the child's home. A network of ceiling-mounted video cameras and microphones are generating approximately 300 gigabytes of observational data each day from the home. One of the worlds largest single-volume disk arrays is under construction to house approximately 400,000 hours of audio and video recordings that will accumulate over the three year study. To analyze the massive data set, we are developing new data mining technologies to help human analysts rapidly annotate and transcribe recordings using semi-automatic methods, and to detect and visualize salient patterns of behavior and interaction. To make sense of large-scale patterns that span across months or even years of observations, we are developing computational models of language acquisition that are able to learn from the childs experiential record. By creating and evaluating machine learning systems that step into the shoes of the child and sequentially process long stretches of perceptual experience, we will investigate possible language learning strategies used by children with an emphasis on early word learning.

This paper addresses the problem of the acquisition of the syntax of propositional logic. An approach based on general purpose cognitive capacities such as invention, adoption, parsing, generation and induction is proposed. Self-organisation principles are used to show how a shared set of preferred lexical entries and grammatical constructions, i.e., a language, can emerge in a population of autonomous agents which do not have any initial linguistic knowledge. Experiments in which a population of autonomous agents constructs a language that allows communicating the formulas of a propositional language are presented. This language although simple has interesting properties found in natural languages, such as compositionality and recursion.

According to the functional approach to language evolution (inspired by cognitive linguistics and construction grammar), grammar arises to deal with issues in communication among autonomous agents, particularly maximisation of communicative success and expressive power and minimisation of cognitive effort. Experiments in the emergence of grammar should hence start from a simulation of communicative exchanges between embodied agents, and then show how a particular issue that arises can be solved or partially solved by introducing more grammar. This paper shows a case study of this approach, focusing on the issue of search during parsing. Multiple hypotheses arise in parsing when the same syntactic pattern can be used for multiple purposes or when one syntactic pattern partly overlaps with another one. It is well known that syntactic ambiguity rapidly leads to combinatorial explosions and hence an increase in memory use and processing power, possibly to a point where the sentence can no longer be handled. Additional grammar, such as syntactic or semantic subcategorisation or word order and agreement constraints can help to dampen search because it provides information to the hearer which hypotheses are the most likely. The paper shows an operational experiment where avoiding search is used as the driver for the introduction and negotiation of syntax. The experiment is also a demonstration of how Fluid Construction Grammar is well suited for experiments in language evolution.

Research into the evolution of grammar requires that we employ formalisms and processing mechanisms that are powerful enough to handle features found in human natural languages. But the formalism needs to have some additional properties compared to those used in other linguistics research that are specifically relevant for handling the emergence and progressive co-ordination of grammars in a population of agents. This document introduces Fluid Construction Grammar, a formalism with associated parsing, production, and learning processes designed for language evolution research. The present paper focuses on a formal definition of the unification and merging algorithms used in Fluid Construction Grammar. The complexity and soundness of the algorithms and their relation to unification in logic programming and other unification-based grammar formalisms are discussed.

We suggest that the primary motivation for an agent to construct a symbol-meaning mapping is to solve a task. The meaning space of an agent should be derived from the tasks that it faces during the course of its lifetime. We outline a process in which agents learn to solve multiple tasks and extract a store of ``cumulative knowledge'' that helps them to solve each new task more quickly and accurately. This cumulative knowledge then forms the ontology or meaning space of the agent. We suggest that by grounding symbols to this extracted cumulative knowledge agents can gain a further performance benefit because they can guide each others' learning process. In this version of the symbol grounding problem meanings cannot be directly communicated because they are internal to the agents, and they will be different for each agent. Also, the meanings may not correspond directly to objects in the environment. The communication process can also allow a symbol meaning mapping that is dynamic. We posit that these properties make this version of the symbol grounding problem realistic and natural. Finally, we discuss how symbols could be grounded to cumulative knowledge via a situation where a teacher selects tasks for a student to perform.

This paper describes efficient word meaning acquisition for infant agents (IAs) based on learning biases that are observed in children's language development. An IA acquires word meanings through learning the relations among visual features of objects and acoustic features of human speech. In this task, the IA has to find out which visual features are indicated by the speech. Previous works introduced stochastic approaches to do this, however, such approaches need many examples to achieve high accuracy. In this paper, firstly, we propose a word meaning acquisition method for the IA based on an Online-EM algorithm without learning biases. Then, we implement two types of biases into it to accelerate the word meaning acquisition. Experimental results show that the proposed method with biases can efficiently acquire word meanings.

In word meaning acquisition through interactions among humans and agents, the efficiency of the learning depends largely on the dialog strategies the agents have. This paper describes automatic acquisition of dialog strategies through interaction between two agents. In the experiments, two agents infer each other's comprehension level from its facial expressions and utterances to acquire efficient strategies. Q-learning is applied to a strategy acquisition mechanism. Firstly, experiments are carried out through the interaction between a mother agent, who knows all the word meanings, and a child agent with no initial word meaning. The experimental results showed that the mother agent acquires a teaching strategy, while the child agent acquires an asking strategy. Next, the experiments of interaction between a human and an agent are investigated to evaluate the acquired strategies. The results showed the effectiveness of both strategies of teaching and asking.

This paper complements the results and analysis shown in current studies on the evolution of signalling and cooperation. It describes operational aspects of the evolved behaviour of a group of robots equipped with a different set of sensors, that navigates towards a target in a walled arena. In particular, analysis of the sound signalling behaviour shows that the robots employ the sound to remain close to each other at a safe distance with respect to the risk of collisions. Spatial discrimination of the sound sources is achieved by exploiting a rotational movement which amplifies intensity differences between the two sound sensors.

The panel will explore the relevance of the emerging tagging systems (Flickr, Del.icio.us, RawSugar and more). Why do they seem to work? What kinds of incentives are required for users to participate? Will tagging survive and scale to mass adoption? What are the behavioral, economic, and social models that underlie each tagging system? What are the dynamics of those systems, and how are they derived from the specific application's design and affordances? We will demand answers to these questions and others from some of the pioneering practitioners and academics in the field. Bring your wireless laptop to participate in a live tagging experiment! The experiment results will be shown and discussed at the end of the panel. To add to the fun, parts of the discussion will be motivated by short video segments.

The emergence of a compositional language with a simple grammar and the effects of individuals popularity on the phylogeny of language are studied based on a multi-agent computational model. In this model, a bottom-up syntactic development is traced, in which the global syntax in sentences is gradually formed from local sequential information. Assuming that the popularity of individuals follows a power-law distribution, we demonstrate that a common language can emerge efficiently only for certain power-law distributions and that these distributions could also be formed as a result of the language phylogeny.

We present a novel experimental method for identifying the inductive biases of human learners. The key idea behind this method is simple: we use participants' re- sponses on one trial to generate the stimuli they see on the next. A theoretical analysis of this ``iterated learn- ing'' procedure, based on the assumption that learners are Bayesian agents, predicts that it should reveal the inductive biases of the learners, as expressed in a prior probability distribution. We test this prediction through two experiments in iterated category learning.

A new model of early language acquisition is introduced. The model demonstrates the staged emergence of lexical and syntactic acquisition. For a period, no linguistic activity is present. The emergence of first words signals the onset of the holophrastic stage that continues to mature without syntactic activity. Syntactic awareness eventually emerges as the result of multiple lexically-based insights. No mechanistic triggers are employed throughout development.

In a recent article, Nakhleh, Ringe and Warnow introduced perfect phylogenetic networks --a model of language evolution where languages do not evolve via clean speciation-- and formulated a set of problems for their accurate reconstruction. Their new methodology assumes networks, rather than trees, as the correct model to capture the evolutionary history of natural languages. They proved the NP-hardness of the problem of testing whether a network is a perfect phy- logenetic one for characters exhibiting at least three states, leaving open the case of binary characters, and gave a straightforward brute-force parameterized algorithm for the problem of running time O(3k n), where k is the number of bidirectional edges in the network and n is its size. In this paper, we first establish the NP-hardness of the binary case of the problem. Then we provide a more efficient parameterized algorithm for this case running in time O(2k n 2). The presented algorithm is very simple, and utilizes some structural results and elegant operations developed in this paper that can be useful on their own in the design of heuristic algorithms for the problem. The analysis phase of the algorithm is very elegant using amortized techniques to show that the upper bound on the running time of the algorithm is much tighter than the upper bound obtained under a conservative worst-case scenario assumption. Our results bear significant impact on reconstructing evolutionary histories of languages --particularly from phonological and morphological character data, most of which exhibit at most two states (i.e., are binary), as well as on the design and analysis of parameterized algorithms.

An important problem for societies of natural and artificial animals is to converge upon a similar language in order to communicate. We call this the language convergence problem. In this paper we study the complexity of finding the optimal (in terms of time to convergence) algorithm for language convergence. We map the language convergence problem to instances of a Decentralized Partially Observable Markov Decision Process to show that the complexity can vary from P-complete to NEXP-complete based on the scenario being studied.

In this paper we describe how a population of simulated robots evolved for the ability to solve a collective navigation problem develop individual and social/communication skills. In particular, we analyze the evolutionary origins of motor and signaling behaviors. Obtained results indicate that signals and the meaning of the signals produced by evolved robots are grounded not only on the robots sensory-motor system but also on robots' behavioral capabilities previously acquired. Moreover, the analysis of the co-evolution of robots individual and communicative abilities indicate how innovation in the former might create the adaptive basis for further innovations in the latter and vice versa.

We study the role of the agent interaction topology in distributed language learning. In particular, we utilize the replicator-mutator framework of language evolution for the creation of an emergent agent interaction topology that leads to quick convergence. In our system, it is the links between agents that are treated as the units of selection and replication, rather than the languages themselves. We use the Noisy Preferential Attachment algorithm, which is a special case of the replicator-mutator process, for generating the topology. The advantage of the NPA algorithm is that, in the short-term, it produces a scale-free interaction network, which is helpful for rapid exploration of the space of languages present in the population. A change of parameter settings then ensures convergence because it guarantees the emergence of a single dominant node which is chosen as teacher almost always

This paper investigates the dynamics of cumulative cultural evolution in a simulation concerning the evolution of language. This simulation integrates the iterated learning model with the Talking Heads experiment in which a population of agents evolves a language to communicate geometrical coloured objects by playing guessing games and transmitting the language from one generation to the next. The results show that cumulative cultural evolution is possible if the language becomes highly regular, which only happens if the language is transmitted from generation to generation.

In the context of minimally cognitive behavior, we used multi-robotic systems to investigate the emergence of communication and cooperation during the evolution of recurrent neural networks. The networks are systematically analyzed to identify their relevant dynamical properties. Evolution efficiently adapts these properties through small structural changes within the networks when specific environmental conditions are altered, such as the number of interacting robots. The findings signify the importance of reducing the predefined knowledge about resulting behaviors, dynamical properties of control, and the topology of neural networks in order to utilize the strength of the Evolutionary Robotics approach to Artificial Life.

We present a neural-competitive learning model of language evolution in which several symbol sequences compete to signify a given propositional meaning. Both symbol sequences and propositional meanings are represented by high-dimensional vectors of real numbers. A neural network learns to map between the distributed representations of the symbol sequences and the distributed representations of the propositions. Unlike previous neural network models of language evolution, our model uses a Kohonen Self-Organizing Map with unsupervised learning, thereby avoiding the computational slowdown and biological implausibility of back-propagation networks and the lack of scalability associated with Hebbian-learning networks. After several evolutionary generations, the network develops systematically regular mappings between meanings and sequences, of the sort traditionally associated with symbolic grammars. Because of the potential of neural-like representations for addressing the symbol-grounding problem, this sort of model holds a good deal of promise as a new explanatory mechanism for both language evolution and acquisition.

We investigate a prototypical agent-based model, the Naming Game, on random geometric networks. The Naming Game is a minimal model, employing local communications that captures the emergence of shared communication schemes (languages) in a population of autonomous semiotic agents. Implementing the Naming Games on random geometric graphs, local communications being local broadcasts, serves as a model for agreement dynamics in large-scale, autonomously operating wireless sensor networks. Further, it captures essential features of the scaling properties of the agreement process for spatially-embedded autonomous agents. We also present results for the case when a small density of long-range communication links are added on top of the random geometric graph, resulting in a ''small-world''-like network and yielding a significantly reduced time to reach global agreement.

Fluid Construction Grammar (FCG) is a new linguistic formalism designed to explore in how far a construction grammar approach can be used for handling open-ended grounded dialogue, i.e. dialogue between or with autonomous embodied agents about the world as experienced through their sensory-motor apparatus. We seek scalable, open-ended language systems by giving agents both the ability to use existing conventions or ontologies, and to invent or learn new ones as the needs arise. This paper contains a brief introduction to the key ideas behind FCG and its current status.

Syntax sets human language apart from other natural communication systems, although its evolutionary origins are obscure. Here we show that free-ranging putty-nosed monkeys combine two vocalizations into different call sequences that are linked to specific external events, such as the presence of a predator and the imminent movement of the group. Our findings indicate that non-human primates can combine calls into higher-order sequences that have a particular meaning.

Humans regularly produce new utterances that are understood by other members of the same language community. Linguistic theories account for this ability through the use of syntactic rules (or generative grammars) that describe the acceptable structure of utterances. The recursive, hierarchical embedding of language units (for example, words or phrases within shorter sentences) that is part of the ability to construct new utterances minimally requires a 'context-free' grammar that is more complex than the 'finite-state' grammars thought sufficient to specify the structure of all non-human communication signals. Recent hypotheses make the central claim that the capacity for syntactic recursion forms the computational core of a uniquely human language faculty. Here we show that European starlings (Sturnus vulgaris) accurately recognize acoustic patterns defined by a recursive, self-embedding, context-free grammar. They are also able to classify new patterns defined by the grammar and reliably exclude agrammatical patterns. Thus, the capacity to classify sequences from recursive, centre-embedded grammars is not uniquely human. This finding opens a new range of complex syntactic processing mechanisms to physiological investigation.

What roles do syntax and semantics have in the grammar of a language? What are the consequences of these roles for syntactic structure, and why does it matter? We sketch the Simpler Syntax Hypothesis, which holds that much of the explanatory role attributed to syntax in contemporary linguistics is properly the responsibility of semantics. This rebalancing permits broader coverage of empirical linguistic phenomena and promises a tighter integration of linguistic theory into the cognitive scientific enterprise. We suggest that the general perspective of the Simpler Syntax Hypothesis is well suited to approaching language processing and language evolution, and to computational applications that draw upon linguistic insights.

Children learn language from their parents and then use the acquired system throughout the rest of their life with little change. At least that is commonly assumed. But a recent paper by Galantucci adds to the growing evidence that adults (and children) are able to create and negotiate complex communication systems from scratch and relatively quickly, without a prior model. This raises questions of what cognitive mechanisms are implied in this joint construction of communication systems, and what the implications are for the origins of human language.

In this paper we introduce a mathematical model of naming games. Naming games have been widely used within research on the origins and evolution of language. Despite the many interesting empirical results these studies have produced, most of this research lacks a formal elucidating theory. In this paper we show how a population of agents can reach linguistic consensus, i.e. learn to use one common language to communicate with one another. Our approach differs from existing formal work in two important ways: one, we relax the too strong assumption that an agent samples infinitely often during each time interval. This assumption is usually made to guarantee convergence of an empirical learning process to a deterministic dynamical system. Two, we provide a proof that under these new realistic conditions, our model converges to a common language for the entire population of agents. Finally the model is experimentally validated.

The human capacity to acquire complex language seems to be without parallel in the natural world. The origins of this remarkable trait have long resisted adequate explanation, but advances in fields that range from molecular genetics to cognitive neuroscience offer new promise. Here we synthesize recent developments in linguistics, psychology and neuroimaging with progress in comparative genomics, gene-expression profiling and studies of developmental disorders. We argue that language should be viewed not as a wholesale innovation, but as a complex reconfiguration of ancestral systems that have been adapted in evolutionarily novel ways.

We show how cultural selection for learnability during the process of linguistic evolution can be visualized using a simple iterated learning model. Computational models of linguistic evolution typically focus on the nature of, and conditions for, stable states. We take a novel approach and focus on understanding the process of linguistic evolution itself. What kind of evolutionary system is this process? Using visualization techniques, we explore the nature of replicators in linguistic evolution, and argue that replicators correspond to local regions of regularity in the mapping between meaning and signals. Based on this argument, we draw parallels between phenomena observed in the model and linguistic phenomena observed across languages. We then go on to identify issues of replication and selection as key points of divergence in the parallels between the processes of linguistic evolution and biological evolution.

What kind of motivation drives child language development? This article presents a computational model and a robotic experiment to articulate the hypothesis that children discover communication as a result of exploring and playing with their environment. The considered robotic agent is intrinsically motivated towards situations in which it optimally progresses in learning. To experience optimal learning progress, it must avoid situations already familiar but also situations where nothing can be learnt. The robot is placed in an environment in which both communicating and non-communicating objects are present. As a consequence of its intrinsic motivation, the robot explores this environment in an organized manner focusing first on non-communicative activities and then discovering the learning potential of certain types of interactive behaviour. In this experiment, the agent ends up being interested by communication through vocal interactions without having a specific drive for communication.

A trait is of adaptive value if it confers a fitness advantage to its possessor. Thus adaptivness is an ahistorical identification of a trait affording some selective advantage to an agent within some particular environment. In results reported here we identify a trait within natural language discourse as having adaptive value by computing a trait/fitness covariance; the possession of the trait correlates with the replication success of the trait's possessor. We show that the trait covaries with fitness across multiple unrelated discursive groups. In our analysis the trait in question is a particular statistically derived word?n? context, that is, a word set. Variation of the word?sage is measured as the relative presence of the word set within a particular text, that is, the percentage of the text devoted to this set of words. Fitness is measured as the rate in which the text is responded to, or replicates, within an online environment. Thus we are studying the micro?volutionary dynamics of natural language discourse.

This paper explores a structure ubiquitous in grammar, the embedded tree, and develops a proposal for how such embedded structures played a fundamental role in the evolution of consonants and vowels. Assuming that linguistic capabilities emerged as a cognitive system from a simply reactive system and that such a transition required the construction of an internal mapping of the system body (cf. Cruse 2003), we propose that this mapping was determined through articulation and acoustics. By creating distinctions between articulators in the vocal tract or by acoustic features of sounds, and then embedding these distinctions, the various possible properties of consonants and vowels emerged. These embedded distinctions represent paradigmatic options for the production of sounds, which provide the basic building blocks for prosodic structure. By anchoring these embedded structures in the anatomy and physiology of the vocal tract, the evolution of phonology itself can be explained by extra-linguistic factors.

Most current modeling for evolution of communication still underplays or ignores the role of local action in spatialized environments: the fact that it is immediate neighbors with which one tends to communicate, and from whom one learns strategies or conventions of communication. Only now are the lessons of spatialization being learned in a related field: game-theoretic models for cooperation. In work on altruism, on the other hand, the role of spatial organization has long been recognized under the term `viscosity'.
Here we offer some simple simulations that dramatize the importance of spatialization for studies of both cooperation and communication, in each case contrasting (a) a model dynamics in which strategy change proceeds globally, and (b) a spatialized model dynamics in which interaction and strategy change both operate purely locally. Local action in a spatialized model clearly favors the emergence of cooperation. In the case of communication, spatialized models allow communication to arise and flourish where the global dynamics more typical in the literature make it impossible.
Simulations make a dramatic case for spatialized modeling, but analysis proves difficult. In a final section we outline some of the surprises of spatial dynamics but also some of the complexity facing attempts at deeper analysis.

To understand evolutionary aspects of communication is to understand the evolutionary development of the meaning relations between language and the world. Such meaning relations are established by the application of the interactive systems of semantic games. Subsumed under the evolutionary framework of repeated games, semantics in such games refers to the cases in which stable meanings survive populations of strategically interacting players. The viability of compositionality, common ground and salience in such evolutionary games is assessed. Foundationally, the discussion is rooted in Charles S. Peirce's pragmatist philosophy.

Previous simulation work on the evolution of communication has not shown how a large signal repertoire could emerge in situated agents. We present an artificial life simulation of agents, situated in a two-dimensional world, that must search for other agents with whom they can trade resources. With strong restrictions on which resources can be traded for others, initially non-communicating agents evolve/learn a signal system that describes the resource they seek and the resource they are willing to offer in return. A large signal repertoire emerges mainly through an evolutionary process. Agents whose production and comprehension abilities rely on a single mechanism fare best, although learning enables agents with separate mechanisms to achieve some measure of success. These results demonstrate that substantial signaling repertoires can evolve in situated multi-agent systems, and suggest that simulated social interactions such as trading may provide a useful context for further computational studies of the evolution of communication.

We study how decentralized agents can develop shared vocabularies without global coordination. Answering this question can help us understand the emergence of many communication systems, from bacterial communication to human languages, as well as helping to design algorithms for supporting self-organizing information systems such as social tagging or ad-word systems for the web. We introduce a formal communication model in which senders and receivers can adapt their communicative behaviors through a type of win-stay lose-shift adaptation strategy. We find by simulations and analysis that for a given number of meanings, there exists a threshold for the number of words below which the agents can't converge to a shared vocabulary. Our finding implies that for a communication system to emerge, agents must have the capability of inventing a minimum number of words or sentences. This result also rationalizes the necessity for syntax, as a tool for generating unlimited sentences.

This article offers a conceptual framework for integrated analysis of subprocesses in action and language, based on goal-directed action. Anatomical substrates are discussed in the companion paper (Arbib and Bota, 2003) which approaches ``Integrative Models of Broca's Area and the Ventral Premotor Cortex'' within the context of explaining why the evolution of the human brain yielded mechanisms which support language in a multi-modal vocal-manual-facial system rather than privileging the vocal mode. Arbib and Bota (2003) examine homologies between different cortical areas in macaque and human to revisit the Mirror System Hypothesis (MSH) of Rizzolatti and Arbib (1998)--the notion that the mirror system for grasping (which has its frontal outpost in premotor area F5 of the macaque) provides the substrate for the evolution of the language-ready brain which supports parity of communication. They also offer a critique and extension based on the work of Aboitiz and Garci(1997; Aboitiz et al., 2006). Arbib and Bota (2003) also discussed the utility of neuroinformatics in relating information across diverse cortical atlases and evaluating degrees of homology for brain regions of interest in different species (for discussion, see Deacon, 2004; Arbib and Bota, 2004).

What processes can explain how very large populations are able to converge on the use of a particular word or grammatical construction without global coordination? Answering this question helps to understand why new language constructs usually propagate along an S-shaped curve with a rather sudden transition towards global agreement. It also helps to analyze and design new technologies that support or orchestrate self-organizing communication systems, such as recent social tagging systems for the web. The article introduces and studies a microscopic model of communicating autonomous agents performing language games without any central control. We show that the system undergoes a disorder/order transition, going trough a sharp symmetry breaking process to reach a shared set of conventions. Before the transition, the system builds up non-trivial scale-invariant correlations, for instance in the distribution of competing synonyms, which display a Zipf-like law. These correlations make the system ready for the transition towards shared conventions, which, observed on the time-scale of collective behaviors, becomes sharper and sharper with system size. This surprising result not only explains why human language can scale up to very large populations but also suggests ways to optimize artificial semiotic dynamics.

We present a mathematical formulation of a theory of language change. The theory is evolutionary in nature and has close analogies with theories of population genetics. The mathematical structure we construct similarly has correspondences with the Fisher-Wright model of population genetics, but there are significant differences. The continuous time formulation of the model is expressed in terms of a Fokker-Planck equation. This equation is exactly soluble in the case of a single speaker and can be investigated analytically in the case of multiple speakers who communicate equally with all other speakers and give their utterances equal weight. Whilst the stationary properties of this system have much in common with the single-speaker case, time-dependent properties are richer. In the particular case where linguistic forms can become extinct, we find that the presence of many speakers causes a two-stage relaxation, the first being a common marginal distribution that persists for a long time as a consequence of ultimate extinction being due to rare fluctuations.

The Naming Game is a model of non-equilibrium dynamics for the self-organized emergence of a linguistic convention or a communication system in a population of agents with pairwise local interactions. We present an extensive study of its dynamics on complex networks, that can be considered as the most natural topological embedding for agents involved in language games and opinion dynamics. Except for some community structured networks on which metastable phases can be observed, agents playing the Naming Game always manage to reach a global consensus. This convergence is obtained after a time generically scaling with the population's size $N$ as $t\_{conv} \sim N^{1.4 \pm 0.1}$, i.e. much faster than for agents embedded on regular lattices. Moreover, the memory capacity required by the system scales only linearly with its size. Particular attention is given to heterogenous networks, in which the dynamical activity pattern of a node depends on its degree. High degree nodes have a fundamental role, but require larger memory capacity. They govern the dynamics acting as spreaders of (linguistic) conventions. The effects of other properties, such as the average degree and the clustering, are also discussed.

The grounding of symbols in computational models of linguistic abilities is one of the fundamental properties of psychologically-plausible cognitive models. This paper presents an embodied model for the grounding of language in action based on epigenetic robots. Epigenetic robotics is one of the new cognitive modeling approaches to modeling autonomous mental development. The robot model is based on an integrative vision of language, in which linguistic abilities are strictly dependent on, and grounded in, other behaviors and skills. It uses simulated robots that learn through imitation the names of basic actions. Robots also learn higher-order action concepts through the process of grounding transfer. The simulation demonstrates how new, higher-order behavioral abilities can be autonomously built upon previously-grounded basic action categories, following linguistic interaction with human users.

The double function of language, as a social/communicative means, and as an individual/cognitive capability, derives from its fundamental property that allows us to internally re-represent the world we live in. This is possible through the mechanism of symbol grounding, i.e. the ability to associate entities and states in the external and internal world with internal categorical representations. The symbol grounding mechanism, as language, has both an individual and a social component. The individual component, called the ``Physical Symbol Grounding'', refers to the ability of each individual to create an intrinsic link between world entities and internal categorical representations. The social component, called ``Social Symbol Grounding'', refers to the collective negotiation for the selection of shared symbols (words) and their grounded meanings. The paper discusses these two aspects of symbol grounding in relation to distributed cognition, using examples from cognitive modeling research on grounded agents and robots.

The paper discusses recent developments in web technologies based on collaborative tagging. This approach is seen as a tremendously powerful way to coordinate the ontologies and views of a large number of individuals, thus constituting the most successful tool for distributed cognition so far.

We consider an extension of the voter model in which a set of interacting elements ( agents) can be in either of two equivalent states (A or B) or in a third additional mixed ( AB) state. The model is motivated by studies of language competition dynamics, where the AB state is associated with bilingualism. We study the ordering process and associated interface and coarsening dynamics in regular lattices and small world networks. Agents in the AB state define the interfaces, changing the interfacial noise driven coarsening of the voter model to curvature driven coarsening. This change in the coarsening mechanism is also shown to originate for a class of perturbations of the voter model dynamics. When interaction is through a small world network the AB agents restore coarsening, eliminating the metastable states of the voter model. The characteristic time to reach the absorbing state scales with system size as tau similar to lnN to be compared with the result tau similar to N for the voter model in a small world network.

A distributed classification paradigm known as collaborative tagging has been successfully deployed in large-scale web applications designed to manage and share diverse online resources. Users of these applications organize resources by associating with them freely chosen text labels, or tags. Here we regard tags as basic dynamical entities and study the semiotic dynamics underlying collaborative tagging. We collect data from a popular system and focus on tags associated with a given resource. We find that the frequencies of tags obey to a generalized Zipf's law and show that a Yule-Simon process with memory can be used to explain the observed frequency distributions in terms of a simple model of user behavior

Recently, there has been a revival of interest in multi-agent simulation techniques for exploring the nature of language change. However, a lack of appropriate validation of simulation experiments against real language data often calls into question the general applicability of these methods in modeling realistic language change. We try to address this issue here by making an attempt to model the phenomenon of schwa deletion in Hindi through a multi-agent simulation framework. The pattern of Hindi schwa deletion and its diachronic nature are well studied, not only out of general linguistic inquiry, but also to facilitate Hindi grapheme-to-phoneme conversion, which is a preprocessing step to text-to-speech synthesis. We show that under certain conditions, the schwa deletion pattern observed in modern Hindi emerges in the system from an initial state of no deletion. The simulation framework described in this work can be extended to model other phonological changes as well.

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.

The models of statistical physics used to study collective phenomena in some interdisciplinary contexts, such as social dynamics and opinion spreading, do not consider the effects of the memory on individual decision processes. On the contrary, in the Naming Game, a recently proposed model of Language formation, each agent chooses a particular state, or opinion, by means of a memory-based negotiation process, during which a variable number of states is collected and kept in memory. In this perspective, the statistical features of the number of states collected by the agents becomes a relevant quantity to understand the dynamics of the model, and the influence of topological properties on memory-based models. By means of a master equation approach, we analyze the internal agent dynamics of Naming Game in populations embedded on networks, finding that it strongly depends on very general topological properties of the system (e.g. average and fluctuations of the degree). However, the influence of topological properties on the microscopic individual dynamics is a general phenomenon that should characterize all those social interactions that can be modeled by memory-based negotiation processes.

We have recently introduced a simple spatial computer simulation model to study the evolution of the linguistic diversity. The model considers processes of selective geographic colonization, linguistic anomalous diffusion and mutation. In the approach, we ascribe to each language a fitness function which depends on the number of people that speak that language. Here, we extend the aforementioned model to examine the role of saturation of the fitness on the language dynamics. We found that the dependence of the linguistic diversity on the area after colonization displays a power law regime with a nontrivial exponent in very good agreement with the measured exponent associated with the actual distribution of languages on the Earth.

We use the formulation of equilibrium statistical mechanics in order to study some important characteristics of language. Using a simple expression for the Hamiltonian of a language system, which is directly implied by the Zipf law, we are able to explain several characteristic features of human language that seem completely unrelated, such as the universality of the Zipf exponent, the vocabulary size of children, the reduced communication abilities of people suffering from schizophrenia, etc. While several explanations are necessarily only qualitative at this stage, we have, nevertheless, been able to derive a formula for the vocabulary size of children as a function of age, which agrees rather well with experimental data.

We use the detrended fluctuation analysis (DFA) and the Grassberger-Proccacia analysis (GP) methods in order to study language characteristics. Despite that we construct our signals using only word lengths or word frequencies, excluding in this way huge amount of information from language, the application of GP analysis indicates that linguistic signals may be considered as the manifestation of a complex system of high dimensionality, different from random signals or systems of low dimensionality such as the Earth climate. The DFA method is additionally able to distinguish a natural language signal from a computer code signal. This last result may be useful in the field of cryptography.

Here we describe how some important scaling laws observed in the distribution of languages on Earth can emerge from a simple computer simulation. The proposed language dynamics includes processes of selective geographic colonization, linguistic anomalous diffusion and mutation, and interaction among populations that occupy different regions. It is found that the dependence of the linguistic diversity on the area after colonization displays two power law regimes, both described by critical exponents which are dependent on the mutation probability. Most importantly for the future prospect of world's population, our results show that the linguistic diversity always decrease to an asymptotic very small value if large areas and sufficiently long times of interaction among populations are considered.

In this work we study the dynamics of language competition. In Abrams and Strogatz [Modeling the dynamics of language death, Nature 424 (2003) 900], the extinction of one of the competing languages is predicted, although in some case the coexistence occurs. The preservation of both languages was explained by Patriarca and Leppanen [Modeling language competition, Physica A 338 (2004) 296] by introducing the existence of two disjoint zones where each language is predominant. However, their results cannot explain the survivance of both languages in only one zone of competition. In this work we discuss their results and propose a new alternative model of Lotka-Volterra type in order to explain the coexistence of two languages.

The bit-string model of Schulze and Stauffer (2005) is applied to non-equilibrium situations and then gives better agreement with the empirical distribution of language sizes. Here the size is the number of people having this language as mother tongue. In contrast, when equilibrium is combined with irreversible mutations of languages, one language always dominates and is spoken by at least 80 percent of the population.

Here, we study a communication model where signals associate to stimuli. The model assumes that signals follow Zipf's law and the exponent of the law depends on a balance between maximizing the information transfer and saving the cost of signal use. We study the effect of tuning that balance on the structure of signal-stimulus associations. The model starts from two recent results. First, the exponent grows as the weight of information transfer increases. Second, a rudimentary form of language is obtained when the network of signal-stimulus associations is almost connected. Here, we show the existence of a sudden destruction of language once a critical balance is crossed. The model shows that maximizing the information transfer through isolated signals and language are in conflict. The model proposes a strong reason for not finding large exponents in complex communication systems: language is in danger. Besides, the findings suggest that human words may need to be ambiguous to keep language alive. Interestingly, the model predicts that large exponents should be associated to decreased synaptic density. It is not surprising that the largest exponents correspond to schizophrenic patients since, according to the spirit of Feinberg's hypothesis, i.e. decreased synaptic density may lead to schizophrenia. Our findings suggest that the exponent of Zipf's law is intimately related to language and that it could be used to detect anomalous structure and organization of the brain.

Studies of the biology of music (as of language) are highly interdisciplinary and demand the integration of diverse strands of evidence. In this paper, I present a comparative perspective on the biology and evolution of music, stressing the value of comparisons both with human language, and with those animal communication systems traditionally termed 'song'. A comparison of the 'design features' of music with those of language reveals substantial overlap, along with some important differences. Most of these differences appear to stem from semantic, rather than structural, factors, suggesting a shared formal core of music and language. I next review various animal communication systems that appear related to human music, either by analogy (bird and whale 'song') or potential homology (great ape bimanual drumming). A crucial comparative distinction is between learned, complex signals (like language, music and birdsong) and unlearned signals (like laughter, ape calls, or bird calls). While human vocalizations clearly build upon an acoustic and emotional foundation shared with other primates and mammals, vocal learning has evolved independently in our species since our divergence with chimpanzees. The convergent evolution of vocal learning in other species offers a powerful window into psychological and neural constraints influencing the evolution of complex signaling systems (including both song and speech), while ape drumming presents a fascinating potential homology with human instrumental music. I next discuss the archeological data relevant to music evolution, concluding on the basis of prehistoric bone flutes that instrumental music is at least 40,000 years old, and perhaps much older. I end with a brief review of adaptive functions proposed for music, concluding that no one selective force (e.g., sexual selection) is adequate to explaining all aspects of human music. I suggest that questions about the past function of music are unlikely to be answered definitively and are thus a poor choice as a research focus for biomusicology. In contrast, a comparative approach to music promises rich dividends for our future understanding of the biology and evolution of music.

Collaborative tagging describes the process by which many users add metadata in the form of keywords to shared content. Recently, collaborative tagging has grown in popularity on the web, on sites that allow users to tag bookmarks, photographs and other content. In this paper we analyze the structure of collaborative tagging systems as well as their dynamical aspects. Specifically, we discovered regularities in user activity, tag frequencies, kinds of tags used, bursts of popularity in bookmarking and a remarkable stability in the relative proportions of tags within a given url. We also present a dynamical model of collaborative tagging that predicts these stable patterns and relates them to imitation and shared knowledge.

The last quarter of the 20th century saw a surge in research in the evolution of language, and this activity continues to grow and extend its influence in the present century. This article is a personal review of some conclusions that can be deemed to have been established in that period. Many of these modern conclusions had ancient precursors as speculative hypotheses with little empirical backing. Modern empirical research in a range of fields has driven foundations deeper, and careful theoretical work has begun to weave a more consistent network of ideas across disciplines. Many mysteries remain, but some clear outlines of the evolutionary bases of humans? most distinctive capacity have begun to emerge. Often the clearer outlines have revealed more complex problems than was vaguely suspected earlier. Three propositions have been selected here, and each will be briefly discussed in a separate section. The three propositions are: 'Language' is not a single monolithic behaviour; Animals have rich conceptual systems; Primates are not necessarily the closest to human-like capacities.

Since many domains are constantly evolving, the associated domain specific languages (DSL) inevitably have to evolve too, to retain their value. But the evolution of a DSL can be very expensive, since existing words of the language (i.e. programs) and tools have to be adapted according to the changes of the DSL itself. In such cases, these costs seriously limit the adoption of DSLs. This paper presents Lever, a tool for the evolutionary development of DSLs. Lever aims at making evolutionary changes to a DSL much cheaper by automating the adaptation of the DSL parser as well as existing words and providing additional support for the correct adaptation of existing tools (e.g. program generators). This way, Lever simplifies DSL maintenance and paves the ground for bottom-up DSL development.

In recent decades, there has been a surge of interest in the origin of language across a wide range of disciplines. Emergentism provides a new perspective to integrate investigations from different areas of study. This paper discusses how the study of language acquisition can contribute to the inquiry, in particular when computer modeling is adopted as the research methodology. An agent-based model is described as an illustration, which simulates how word order in a language could have emerged at the very beginning of language origin. Two important features of emergence, heterogeneity and nonlinearity, are demonstrated in the model, and their implications for applied linguistics are discussed.

It has long been claimed that Homo sapiens is the only species that has symbolic language, but only recently recognized that humans also have an unusual pattern of growth and development. Social mammals have two stages of pre-adult development: infancy and juvenility. Humans have two additional prolonged and pronounced life history stages: childhood---an interval of four years extending between infancy and the juvenile period that follows---and adolescence---a stage of about eight years that stretches from juvenility to adulthood. We begin by reviewing the primary biological and linguistic changes occurring in each of the four preadult ontogenetic stages in life history. Then we attempt to trace the evolution of childhood and juvenility in our hominid ancestors. We propose that several different forms of selection applied in infancy and childhood; and that in adolescence, elaborated vocal behaviors played a role in courtship and intrasexual competition, enhancing fitness and ultimately integrating performative and pragmatic skills with linguistic knowledge in a broad faculty of language. A theoretical consequence of our proposal is that fossil evidence of the uniquely human stages may be used, with other findings, to date the emergence of language. If important aspects of language cannot appear until sexual maturity, as we propose, then a second consequence is that the development of language requires the whole of modern human ontogeny. Our life history model thus offers new ways of investigating, and thinking about, the evolution, development, and ultimately the nature of human language.

We suggest that human culture exhibits key Darwinian evolutionary properties, and argue that the structure of a science of cultural evolution should share fundamental features with the structure of the science of biological evolution. This latter claim is tested by outlining the methods and approaches employed by the principal subdisciplines of evolutionary biology and assessing whether there is an existing or potential corresponding approach to the study of cultural evolution. Existing approaches within anthropology and archaeology demonstrate a good match with the macroevolutionary methods of systematics, paleobiology, and biogeography, whereas mathematical models derived from population genetics have been successfully developed to study cultural microevolution. Much potential exists for experimental simulations and field studies of cultural microevolution, where there are opportunities to borrow further methods and hypotheses from biology. Potential also exists for the cultural equivalent of molecular genetics in ``social cognitive neuroscience,'' although many fundamental issues have yet to be resolved. It is argued that studying culture within a unifying evolutionary framework has the potential to integrate a number of separate disciplines within the social sciences.

Many scholars working in the field of language evolution interpret the Baldwin Effect (i.e. the hypothesis that learned behaviors may become inherited, thus affecting the direction of evolutionary change) as a powerful evolutionary mechanism. Baldwin's proposal, however, is highly controversial, in that the empirical support for it is far from conclusive. The aim of this article is to critically examine one of the main sources of evidence adduced in support of the Baldwin Effect, namely its alleged parity, as repeatedly assumed in Briscoe's (2000, 2002, 2003, 2005) approach to language phylogeny, with Waddington's genetic assimilation. It is argued here, however, that Baldwin's and Waddington's mechanisms are fundamentally different, and that this has important consequences for Briscoe's evolutionary model.

Anthropologists and archaeologists increasingly use phylogenetic methods to test hypotheses involving cross-cultural traits, but the appropriateness of applying tree-based methods to analyze cultural traits is unclear. The authors developed a spatially explicit computer simulation model to investigate trait evolution in relation to phylogeny and geography and used the simulation to assess the sensitivity of two comparative methods (independent contrasts and partial Mantel tests) to different degrees of horizontal transmission. Simulation results show that (a) the method of independent contrasts is sensitive to even small amounts of horizontal transmission in cultural data sets, (b) Mantel tests fail to cleanly discriminate between datasets characterized by different levels of horizontal and vertical trait transmission, and (c) partial Mantel tests do not produce markedly improved statistical performance when testing for associations among traits (as compared to independent contrasts). The results highlight the need for empirical estimates of horizontal transmission and extinction rates in cross-cultural datasets.

Our earlier language model is modified to allow for the survival of a minority language without higher status, just because of the pride of its speakers in their linguistic identity. An appendix studies the roughness of the interface for linguistic regions when one language conquers the whole territory.

The understanding of language competition helps us to predict extinction and survival of languages spoken by minorities. A simple agent-based model of a sexual population, based on the Penna model, is built in order to find out under which circumstances one language dominates other ones. This model considers that only young people learn foreign languages. The simulations show a first order phase transition of the ratio between the number of speakers of different languages with the mutation rate as control parameter.

We consider the spreading and competition of languages that are spoken by a population of individuals. The individuals can change their mother tongue during their lifespan, pass on their language to their offspring and finally die. The languages are described by bitstrings, their mutual difference is expressed in terms of their Hamming distance. Language evolution is determined by mutation and adaptation rates. In particular we consider the case where the replacement of a language by another one is determined by their mutual Hamming distance. As a function of the mutation rate we find a sharp transition between a scenario with one dominant language and fragmentation into many language clusters. The transition is also reflected in the Hamming distance between the two languages with the largest and second to largest number of speakers. We also consider the case where the population is localized on a square lattice and the interaction of individuals is restricted to a certain geometrical domain. Here it is again the Hamming distance that plays an essential role in the final fate of a language of either surviving or being extinct.

We study the exchange of information in collective informa- tion systems mediated by information agents, focusing specifically on the problem of semantic interoperability. We advocate the use of mecha- nisms inspired from natural language, that enable each agent to develop a repertoire of grounded categories and labels for these categories and negotiate their use with other agents. The communication system as well as its semantics is hence emergent and adaptive instead of predefined. It is the result of a self-organised semiotic dynamics where relations be- tween data, labels for the data, and the categories associated with the labels undergo constant evolution.

Semiotic dynamics involves the processes whereby groups of people or artificial agents collectively invent and negotiate shared semiotic systems, which they use for communication or information organization. Tagging systems (such as Flickr, CiteULike, del.icio.us, or connotea) offer examples of human semiotic dynamics at work, aided by technologies such as the Internet but also by a new sense of collective action in an increasingly connected world. Semiotic dynamics builds on many earlier AI developments: the insights into and technologies of semantic networks and knowledge representation from the seventies, the ideas on embodiment and grounding from the late eighties, and the perspective of multiagent systems from the nineties. But all these aspects join together into a new vision on intelligence, with the social, collective dynamics of representation-making at the center. These new AI developments don't stand in isolation; they resonate with recent developments in linguistics, psychology, and the mathematical study of networks. This article briefly illustrates the current study of semiotic dynamics, the resulting technologies, and the field's impact on current and future intelligent systems applications. This article is part of a special issue on the Future of AI.

The recent blossoming of evolutionary linguistics has resulted in a variety of theories that attempt to provide a selective scenario for the evolution of early language. However, their overabundance makes many researchers sceptical of such theorising. Here, we suggest that a more rigorous approach is needed towards their construction although, despite justified scepticism, there is no agreement as to the criteria that should be used to determine the validity of the various competing theories. We attempt to fill this gap by providing criteria upon which the various historical narratives can be judged. Although individually none of these criteria are highly constraining, taken together they could provide a useful evolutionary framework for thinking about the evolution of human language.

Word usage is of interest to linguists for its own sake as well as to social scientists and others seeking to track the spread of ideas, for example in public debates over political decisions. The historical evolution of language can be analysed with the tools of corpus linguistics through evolving corpora and the web. But word usage statistics can only be gathered for known words. In this article, techniques are described and tested for identifying new words from the web, focussing on the case when the words are related to a topic and have a hybrid form with a common sequence of letters. The results highlight the need to employ a combination of search techniques and show the wide potential of hybrid word family investigations in linguistics and social science.

Evidence supporting a rich memory for associations suggests that people can store perceptual details in the form of exemplars. The resulting particulate model of category contents allows the application of evolution theory in modeling category change, because variation in categorized percepts is reflected in the distribution of exemplars in a category. Within a production-perception feedback loop, variation within an exemplar-based category provides a reserve of variants that can serve as the seeds for shifts in the system over time through random or selection-driven asymmetries in production and perception. Here, three potential pathways for evolutionary change are identified in linguistic categories: pruning of lines of inheritance, blending inheritance and natural selection. Simulations of each of these pathways are shown within a simple exemplar-based model of category production and perception, showing how consideration of evolutionary processes may contribute to our understanding of linguis...

We show the presence of genuine quantum structures in human language. The neo-Darwinian evolutionary scheme is founded on a probability structure that satisfies the Kolmogorovian axioms, and as a consequence cannot incorporate quantum-like evolutionary change. In earlier research we revealed quantum structures in processes taking place in conceptual space. We argue that the presence of quantum structures in language and the earlier detected quantum structures in conceptual change make the neo-Darwinian evolutionary scheme strictly too limited for Evolutionary Epistemology. We sketch how we believe that evolution in a more general way should be implemented in epistemology and conceptual change, but also in biology, and how this view would lead to another relation between both biology and epistemology.

In this paper we motivate and report on the implementation of a computer experiment to investigate the syntax and semantics of linguistic constructions about time. It is argued that the way in which a domain like time is conceptualized is not universal and evolves over time. To investigate this we want to simulate a population of agents evolving their proper language and ontology of time in order to succeed in communicating temporal information. Such simulations can be done using a formalism proposed by Steels (2004). Some advances in applying the formalism to the domain of time are reported and examples of actual simulations are presented.

This paper describes the uses of computer models in studying the evolution of language. Language is a complex dynamic system that can be studied at the level of the individual and at the level of the population. Much of the dynamics of language evolution and language change occur because of the interaction of these two levels. It is argued that this interaction is too complicated to study with pen-and-paper analysis alone and that computer models therefore provide a useful tool for understanding language evolution. Different techniques are presented: direct optimization, genetic algorithms and agent-based models. Of each of these techniques, an example is briefly presented. Also, the importance of correctly measuring and presenting the results of computer simulations is stressed.

A familiar complaint about statisticians and applied mathematicians is that they are the possessors of a relatively small number of rather elegant hammers with which they roam the world seeking convenient nails to pound, or at least screws they can pretend are nails. One all too often hears tales of scholars who have begun to describe the details of their particular research problem to a statistician, only to have the statistician latch on to a few phrases early in the conversation and then glibly announce that the problem is an exemplar of a standard one in statistics that has a convenient, pre-packaged solution - preferably one that uses some voguish, recently developed technique (bootstrap, wavelets, Markov chain Monte Carlo, hidden Markov models,...)

propose here to give detailed or specific critiques of these, which are available elsewhere, but look at the broader problem behind the failure to achieve an interdisciplinary consensus on how phylogenetic methods, initially developed for applications outside linguistics, can ...

The inference of evolutionary history, whether in biology or in linguistics, is aided by a carefully considered model of the evolutionary process and a reconstruction method which is expected to produce a reasonably accurate estimation of the true evolutionary history when the real data match the model assumptions and are of sufficient quantity. In molecular systematics (i.e., the inference of evolutionary histories from molecular data), much of the research effort has focused in two areas: first, the development of increasingly parameter rich models of molecular sequence evolution, and second, the development of increasingly sophisticated software tools and algorithms for reconstructing phylogenies under these models. The plethora of software for reconstructing phylogenies from molecular data is staggering. By comparison, much less has been done in historical linguistics in terms of developing statistical models of character evolution or reconstruction methods, suggesting that there is perhaps much to be gained by doing so. ...

It is hard to imagine how the development of quantitative linguistics would have been after GK Zipf's untimely death without the work of G. Altmann. This article aims to honour a living giant of the Zipfian school of linguistics, and presents some findings that contradict the ...

In the course of natural history, Evolution has come up with several great innovations, such as nucleic acids, proteins, cells, chromosomes, multi-cellular organisms, the nervous system.... The last ``invention'' which truly revolutionized the very rules of evolution is language. It gives us an unprecedented possibility to transmit information from generation to generation not by the ``traditional'' means of a genetic code, but by talking. This new mode of cross-generational information transfer has given rise to the so-called ``cultural evolution''. It is responsible for a big part of being ``human''. It is shaping the history and changing the rules of biology. Without exaggeration, it is one of the most fascinating traits of Homo Sapiens.

Language is a culturally transmitted system -- children learn the language of their speech community on the basis of the linguistic behavior of that community. This cultural transmission can lead to the cultural evolution of the linguistic system, whereby language changes over time as a consequence of pressures acting on it during its cultural transmission.

Cultural evolution potentially offers an explanation for the origins of a linguistic system with the design features and functionality of human language, as well as an explanation for the subsequent change of such systems -- the processes that explain the ways in which languages change on a historical timescale can also explain how languages themselves emerged.
...

We describe a simulation model of language evolution which integrates synergetic linguistics with multi-agent modeling. On the one hand, this enables to utilize knowledge about the distribution of the parameter values of system variables as a touch stone of simulation validity. On the other hand it allows to account for synergetic interdependencies of microscopic system variables and macroscopic order parameters. This approach goes beyond the classical setting of synergetic linguistics by grounding processes of selfregulation and -organization in mechanisms of (dialogically aligned) language learning. Consequently, the simulation model includes four levels, that are, (i) the level of single information processing agents which are (ii) dialogically aligned in communication processes enslaved (iii) by the social system in which the agents participate and whose countless communication events shape (iv) the corresponding language system. In summary, the present paper is basically conceptual. It outlines a simulation model which bridges between different levels of language modeling kept apart in contemporary simulation models. This model relates to artificial cognition systems in the sense that it may be implemented to endow an artificial agent community in order to perform distributed processes of meaning constitution.

Lightfoot (1999) proposes the following explanation for the loss of the verb-second rule in Middle English: There were two regional dialects of Middle English, a northern dialect influenced by Old Norse with a verb- second rule, and a southern dialect with a slightly different word order. Children acquire the verb-second rule based on hearing some critical fraction of cue sentences requiring such a rule. As the dialects experienced increased contact, northern children were less likely to hear enough cue sentences, and consequently acquired a different grammar, resulting in the extinction of the northern dialect.

This hypothesis can be modeled with differential equations. By using dynamical systems methods, the catastrophe in question may be modeled by a mathematical event known as a saddle-node bifurcation. A key part of the model is the function that gives the probability of learning the northern dialect given that a fraction of the local population uses it. Other model acquisition algorithms, such as memoryless learner (Niyogi \& Berwick 1996), give the mysterious result that verb-second languages should be extremely stable, in contrast to the history of English. This new model provides an explanation for that behavior: Memoryless learners are more sensitive to noise, resulting in a differently shaped function that does not allow the northern grammar to disappear. This model demonstrates how dynamical systems theory can be used to study language change and learning models.

Language is often thought of as the crowning human adaptation, the one that allowed Homo sapiens sapiens to conquer the globe. The assumption underlying such ideas is that verbal transmission of information provides unalloyed benefits, by reducing the costs of learning about the environment. However, this raises the question of why no other species has discovered such a good trick. I argue that verbal transmission is only likely to be adaptive in a restricted range of circumstances. Even then, it cannot be exclusively relied on, and it causes problems of deceit and instances of maladaptation. We should expect natural selection to have made us discriminating evaluators of verbal information who ultimately trust the evidence of our senses. Nonetheless, once language has become widespread, it can increase human adaptability, by increasing the efficiency of individual learning.

The emergence of complex language is one of the fundamental hallmarks of human evolution. It shaped and constrained the emergence of social structures and makes us different from other animals. Beyond their differences, several remarkable features indicate the presence of fundamental principles of organization shared by all known languages. The best known is the so called Zipf's law, which states that the frequency of a word decays as a (universal) power law of its rank. A different, but related property of human language involves the architecture of word interactions. It has been recently shown that linguistic webs of different types display a global organization that is not very different from the ones observed in other natural and artificial complex networks, from the genome to the internet. In this chapter we explore the statistical features displayed by these seemingly universal laws and their possible origins. It is shown that fundamental principles of organization pervade the origin of power laws in human language and shape its evolutionary history.

Mirror neurons may hold the brain's key to social interaction - each coding not only a particular action or emotion but also the recognition of that action or emotion in others. The Mirror System Hypothesis adds an evolutionary arrow to the story - from the mirror system for hand actions, shared with monkeys and chimpanzees, to the uniquely human mirror system for language. In this volume, written to be accessible to a wide audience, experts from child development, computer science, linguistics, neuroscience, primatology and robotics present and analyze the mirror system and show how studies of action and language can illuminate each other. Topics discussed in the fifteen chapters include: What do chimpanzees and humans have in common? Does the human capability for language rest on brain mechanisms shared with other animals? How do human infants acquire language? What can be learned from imaging the human brain? How are sign- and spoken-language related? Will robots learn to act and speak like humans?

TABLE OF CONTENTS
Preface
Part I. Two Perspectives:
1. The mirror system hypothesis on the linkage of action and languages Michael Arbib
2. The origin and evolution of language: a plausible, strong-AI account Jerry Hobbs
Part II. Brain, Evolution and Comparative Analysis:
3. Cognition, imitation and culture in the great apes Craig Stanford
4. The signer as an embodied mirror neuron: neural systems underlying sign language and action Karen Emmorey
5. Neural homologies and the grounding of neurolinguistics Michael Arbib and Mihail Bota
Part III. Dynamical Systems in Action and Language:
6. Dynamical systems: brain, body and imitation Stefan Schaal
7. The role of vocal tract gestural action units in understanding the evolution of phonology Louis Goldstein, Dani Byrd and Elliot Saltzman
8. Lending a helping hand to hearing: a motor theory of speech perception Jeremy I. Skipper, Howard C. Nusbaum and Steven L. Small
Part IV. From Mirror System to Syntax and Theory of Mind:
9. Attention and the minimal subscene Laurent Itti and Michael Arbib
10. Action verbs, argument structure constructions, and the mirror neuron system David Kemmerer
11. Linguistic corpora and theory of mind Andrew Gordon
Part V. Development of Action and Language:
12. The development of grasping and the mirror system Erhan Oztop, Nina Bradley and Michael Arbib
13. Development of goal-directed imitation, object manipulation and language in humans and robots Iona D. Goga and Aude Billard
14. Affordances, effectivities and the mirror system in child development Patricia Zukow-Goldring
15. Implications of mirror neurons for the ontogeny and phylogeny of cultural processes: the examples of tools and language Patricia Greenfield.

TABLE OF CONTENTS
Preface
1. The Mark of Evolution
2. Primitive and Derived Features of Language
3. The Singularity of Speech
4. The Neural Bases of Language
5. Motor Control and the Evolution of Language
6. The Gift of Tongue
7. Linguistic Issues
8. Where We Might Go

TABLE OF CONTENTS

I The Problem 5
1 Introduction 7

II Language Learning 51
2 Language Acquisition - Induction 53
3 Language Acquisition - Linguistics I 89
4 Language Acquisition - Linguistics II 127

III Language Change 163
5 Language Change - A Preliminary Model 165
6 Language Change - n Languages 197
7 An Application to Portuguese 243
8 An Application to Chinese 261
9 Cultural Evolution 285
10 Variations and Case Studies 317

IV The Origin of Language 353
11 Communicative EAeiency 355
12 Linguistic Coherence and Communicative Fitness 389
13 Linguistic Coherence and Social Learning 421

V Conclusions 459
14 Conclusions 461

Preface

This monograph explores the interplay between learning and evolution in the context of linguistic systems. For several decades now, the process of language acquisition has been conceptualized as a procedure that maps lin- guistic experience onto linguistic knowledge. If linguistic knowledge is char- acterized in computational terms as a formal grammar and the mapping procedure is algorithmic, this conceptualization admits computational and mathematical modes of inquiry into language learning. Indeed, such a view is implicit in most modern approaches to the subject in linguistics, cognitive science, and artificial intelligence.

Now learning (acquisition) is the mechanism by which language is trans- mitted from old speakers to new. Therefore, the evolution of language over generational time in linguistic populations will depend upon the learning procedure used by the individuals in it. Yet the interplay between learn- ing by the individual and evolution of the population can be quite subtle. We need tools to reason about the phenomena and elucidate the precise na- ture of the relationships involved. To this end, this monograph presents a framework in which to conduct such an analysis.

...

TABLE OF CONTENTS
Preface
1. Introduction
2. What Evolution Is
3. Fitness Landscapes and Sequence Spaces
4. Evolutionary Games
5. Prisoners of the Dilemma
6. Finite Populations
7. Games in Finite Populations
8. Evolutionary Graph Theory
9. Spatial Games
10. HIV Infection
11. The Evolution of Virulence
12. The Evolutionary Dynamics of Cancer
13. Language Evolution
14. Conclusion

Speech is the principal supporting medium of language. In this book Pierre-Yves Oudeyer considers how spoken language first emerged. He presents an original and integrated view of the interactions between self-organization and natural selection, reformulates questions about the origins of speech, and puts forward what at first sight appears to be a startling proposal - that speech can be spontaneously generated by the coupling of evolutionarily simple neural structures connecting perception and production. He explores this hypothesis by constructing a computational system to model the effects of linking auditory and vocal motor neural nets. He shows that a population of agents which used holistic and unarticulated vocalizations at the outset are inexorably led to a state in which their vocalizations have become discrete, combinatorial, and categorized in the same way by all group members. Furthermore, the simple syntactic rules that have emerged to regulate the combinations of sounds exhibit the fundamental properties of modern human speech systems.

Table of Contents
1. The Self-Organization Revolution in Science
2. The Human Speech Code
3. Self-Organization and Evolution
4. Existing Theories
5. Artificial Systems as Research Tools for Natural Sciences
6. The Artificial System
7. Learning Perceptuo-Motor Correspondences
8. Strong Combinatoriality and Phonotactics
9. New Scenarios
10. Constructing for Understanding

This thesis investigates the evolutionary plausibility of the Minimalist Program. Is such a theory of language reasonable given the assumption that the human linguistic capacity has been subject to the usual forces and processes of evolution? More generally, this thesis is a comment on the manner in which theories of language can and should be constrained. What are the constraints that must be taken into account when constructing a theory of language? These questions are addressed by applying evidence gathered in evolutionary biology to data from linguistics.

The development of generative syntactic theorising in the late 20th century has led to a much redesigned conception of the human language faculty. The driving question - `why is language the way it is' - has prompted assumptions of simplicity, perfection, optimality, and economy for language; a minimal system operating in an economic fashion to fit into the larger cognitive architecture in a perfect manner. Studies in evolutionary linguistics, on the other hand, have been keen to demonstrate that language is complex, redundant, and adaptive, Pinker & Bloom's (1990) seminal paper being perhaps the prime example of this. The question is whether these opposing views can be married in any way.

Interdisciplinary evidence is brought to bear on this problem, demonstrating that any reconciliation is impossible. Evolutionary biology shows that perfection, simplicity, and economy do not arise in typically evolving systems, yet the Minimalist Program attaches these characteristics to language. It shows that evolvable systems exhibit degeneracy, modularity, and robustness, yet the Minimalist Programmust rule these features out for language. It shows that evolution exhibits a trend towards complexity, yet the Minimalist Program excludes such a depiction of language.

By determining where language falls in each of these three cases, the choice between the opposing positions of gradual adaptive evolution and the Minimalist Program is resolved. Language is shown to be imperfect, uneconomic, and non-optimal, and hence a typical biological system. Language is shown to exhibit the key features of evolvability, and hence accords with the usual pressures and constraints of evolution. Language is shown to be both complex and adaptive, and hence amenable to a gradual adaptive evolutionary account.

In addition, the uniqueness of the pivotal property of language according to one minimalist evolutionary account - recursion - is examined, its place as just one of a collection of properties which make language special illustrating that language is significantly more complex and sophisticated than the Minimalist Program allows. Finally, significant flaws in the details of minimalist theories themselves - including extraneous operations, and unmotivated and stipulative features - are uncovered, further signalling that the perfection, simplicity, and economy that minimalism advocates is not a valid characterisation of language.

This thesis inquires into how human language relates to morality -- and shows the ways language enables, extends, and maintains human value systems. Though we ultimately need to view the relation between language and morality from many different perspectives -- biological, psychological, sociological, and philosophical -- the approach here is primarily a linguistic one informed by evolutionary theory.

At first, this study shows how natural selection relates to the problem of altruism and how language serves human moral ontogeny. Subsequently, the argument demonstrates how language helps enable cultural group selection. Moreover, as language helps influence human behavior in an altruistic direction beyond in-group non-kin (helping facilitate cultural group selection), we also consider how language can help facilitate altruistic behavior towards out-group non-kin. This therefore raises the prospect of a limited moral realism in a world of evolutionary processes.

With these issues and possibilities in mind, we consider and analyze the properties of language that help extend human morality. Specifically, discussion covers how recursion, linguistic creativity, naming ability, displacement, stimulus freedom, compositionality, cultural transmission, and categorization extend moral systems. Moreover, because language so broadly influences morality, the inquiry extends into how linguistic differences (specifically between English and Japanese) might also cause subtle differences in moral perception between Japanese and English speakers.

Lastly, we consider how moral ideas might take on a life of their own, catalytically propagating in degrees dependent and independent of human intention. That is, we consider how ideas might become memetic. After considering the serious problems of memetics, this approach employs a linguistic version of memetic theory and considers how psychological, social, and linguistic constraints may cause moral memes to attain a memetic state and spread by an independent or semi-independent replicator dynamic. Thus, some moral ideas that we possess through language may actually possess us.