Language Evolution and Computation Bibliography

The complexity, variation, and change of languages make evident the importance of representation and learning in the acquisition and evolution of language. For example, analytic studies of simple language in unstructured populations have shown complex dynamics, depending on the fidelity of language transmission. In this study we extend these analysis of evolutionary dynamics to include grammars inspired by the principles and parameters paradigm. In particular, the space of languages is structured so that some pairs of languages are more similar than others, and mutations tend to change languages to nearby variants. We found that coherence emerges with lower learning fidelity than predicted by earlier work with an unstructured language space.

The question of language evolution is of interest to linguistics, biology and recently, engineering communicating networks. Previous work on these problems has focused mostly on a fully-connected population. We are extending this study to structured populations, which are generally more realistic and offer rich opportunities for linguistic diversification. Our work focuses on the convergence properties of a spatially structured population of learners acquiring a language from one another. We investigate several metrics, including mean language coherence and the critical learning fidelity threshold.

This paper presents a computational framework for studying the influence of learning on the evolution of avian communication. We conducted computer simulations for exploring the effects of different learning strategies on the evolution of bird song. Experimental results show the genetic assimilation of song repertoires as a consequence of interactions between learning and evolution.

In an effort to better guide research into self-configuring wireless sensor networks, we discuss a technical definition of the term self-organization. We define a self-organizing system as one where a collection of units coordinate with each other to form a system that adapts to achieve a goal more efficiently. We then lay out some conditions that must hold for a system to meet this definition and discuss some examples of self-organizing systems. Finally, we explore some of the ways this definition applies to wireless sensor networks.

This paper presents a computational framework for studying the influence of learning on the evolution of communication. In our model, an evolving population of learning agents is engaged in pairwise comunicative interactions. Simulation results show the genetic assimilation of trasmission behaviors as a consequence of saussurean learning.

This paper describes a framework for studies of the adaptive acquisition and evolution of language, with the following components: language learning begins by associating words with cognitively salient representations (``grounding''); the sentences of each language are determined by properties of lexical items, and so only these need to be transmitted by learning; the learnable languages allow multiple agreements, multiple crossing agreements, and reduplication, as mildly context sensitive and human languages do; infinitely many different languages are learnable; many of the learnable languages include infinitely many sentences; in each language, inferential processes can be defined over succinct representations of the derivations themselves; the languages can be extended by innovative responses to communicative demands. Preliminary analytic results and a robotic implementation are described.

For many adaptive complex systems information about the environment is not simply recorded in a look-up table, but is rather encoded in a theory, schema, or model, which compresses the information. The grammar of a language can be viewed as such a schema or theory. In a prior study [Teal et al., 1999] we proposed several conjectures about the learning and evolution of language that should follow from these observations: (C1) compression aids in generalization; (C2) compression occurs more easily in a smooth, as opposed to a rugged, problem space; and (C3) constraints from compression make it likely that natural languages eveolve toward smooth string spaces. This previous work found general, if not complete support for these three conjectures. Here we build on that study to clarify the relationship between Minimum Description Length (MDL) and error in our model and examine evolution of certain languages in more detail. Our results suggest a fourth conjecture: that all else being equal, (C4) more complex languages change more rapidly during evolution.

What permits some systems to evolve and adapt more effectively than others? Gell-Mann [3] has stressed the importance of ``com- pression'' for adaptive complex systems. Information about the environ- ment is not simply recorded as a look-up table, but is rather compressed in a theory or schema. Several conjectures are proposed: (I) compression aids in generalization; (II) compression occurs more easily in a ``smooth'', as opposed to a ``rugged'', string space; and (III) constraints from com- pression make it likely that natural languages evolve towards smooth string spaces. We have been examining the role of such compression for learning and evolution of formal languages by artificial agents. Our sys- tem does seem to conform generally to these expectations, but the trade- oobetween compression and the errors that sometimes accompany it need careful consideration.

This paper investigates the evolution of communication among autonomous robots in the real world. A simple model has been constructed as a first step, in which a population of artificial organisms inhabits a lattice plane. Each organism communicates information with neighbors by uttering words. A common language typically evolves. We have analyzed evolutionary dynamics in this system, and have begun to implement it with a population of small mobile robots.