The complexity of finding an optimal policy for language convergence

Kiran Lakkaraju, Les Gasser

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings
PublisherSpringer-Verlag Berlin Heidelberg
Pages804-815
Number of pages12
ISBN (Print)3540386084, 9783540386087
DOIs
StatePublished - 2006
Event9th International Conference on Simulation of Adaptive Behavior, SAB 2006 - Rome, Italy
Duration: Sep 25 2006Sep 29 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4095 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Conference on Simulation of Adaptive Behavior, SAB 2006
CountryItaly
CityRome
Period9/25/069/29/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'The complexity of finding an optimal policy for language convergence'. Together they form a unique fingerprint.

Cite this