Related links

Authoritative: http://dx.doi.org/10.1007/11840541_66   (Publisher's PDF... likely be available here.)

Web search: Google Web Search   ::   Google Scholar

Abstract

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.

@inproceedings{lakkaraju06SAB,
  author={Kiran Lakkaraju and Les Gasser},
  title={The Complexity of Finding an Optimal Policy for Language Convergence},
  year={2006},
  pages={804-815},
  editor={Nolfi, S. and et al.},
  publisher={Springer Verlag},
  booktitle={SAB06},
  doi={10.1007/11840541_66},
  url={http://www.isrl.uiuc.edu/~amag/langev/paper/lakkaraju06SAB.html}
}