Language Evolution and Computation Bibliography

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

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

We describe the reconstruction of a phylogeny for a set of taxa, with a character-based cladistics approach, in a declarative knowledge representation formalism, and show how to use computational methods of answer set programming to generate conjectures about the evolution of the given taxa. We have applied this computational method in two domains: to historical analysis of languages, and to historical analysis of parasite-host systems. In particular, using this method, we have computed some plausible phylogenies for Chinese dialects, for Indo-European language groups, and for Alcataenia species. Some of these plausible phylogenies are different from the ones computed by other software. Using this method, we can easily describe domain specific information (e.g. temporal and geographical constraints), and thus prevent the reconstruction of some phylogenies that are not plausible.

The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about contacts between prehistoric linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages.

Researchers interested in the history of the Indo-European family of languages have used a variety of methods to estimate the phylogeny of the family, and have obtained widely differing results. In this paper we explore the reconstructions of the Indo- European phylogeny obtained by using the major phylogeny estimation procedures on an existing database of 336 characters (including lexical, phonological, and morpho- logical characters) for 24 Indo-European languages. Our study finds that the different methods agree in part, but that there are also several striking differences. We dis- cuss the reasons for these differences, and make proposals with respect to phylogenetic reconstruction in historical linguistics.

The evolutionary history of languages can be modeled as a tree, called a phylogeny, where the leaves represent the extant lan- guages, the internal vertices represent the ancestral languages, and the edges represent the genetic relations between the languages. Languages not only inherit characteristics from their ancestors but also sometimes borrow them from other languages. Such borrowings can be represented by additional non-tree edges. This paper addresses the problem of com- puting a small number of additional edges that turn a phylogeny into a 'perfect phylogenetic network'. To solve this problem, we use answer set programming, which represents a given computational problem as a logic program whose answer sets correspond to solutions. Using the answer set solver smodels, with some heuristics and optimization tech- niques, we have generated a few conjectures regarding the evolution of Indo-European languages.

This paper reports the results of an attempt to recover the first-order subgrouping of the Indo-European family using a new computational method devised by the authors and based on a 'perfect phylogeny' algorithm. The methodology is also briefly described, and points of theory and methodology are addressed in connection with the experiment whose results are here reported.

In this paper we present a new methodology for determining the evolutionary history of related languages. Our methodology uses linguistic information encoded as qualitative characters, and provides much greater precision than previous methods. Our analysis of Indo- European (IE) languages resolves questions that have troubled scholars for over a century.