The complexity of finding an optimal policy for language convergence

Kiran Lakkaraju; Les Gasser

doi:10.1007/11840541_66

The complexity of finding an optimal policy for language convergence

Kiran Lakkaraju, Les Gasser

School of Information Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings
Publisher	Springer-Verlag Berlin Heidelberg
Pages	804-815
Number of pages	12
ISBN (Print)	3540386084, 9783540386087
DOIs	https://doi.org/10.1007/11840541_66
State	Published - 2006
Event	9th International Conference on Simulation of Adaptive Behavior, SAB 2006 - Rome, Italy Duration: Sep 25 2006 → Sep 29 2006

Publication series

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

Other

Other	9th International Conference on Simulation of Adaptive Behavior, SAB 2006
Country	Italy
City	Rome
Period	9/25/06 → 9/29/06

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/11840541_66

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

Lakkaraju, K., & Gasser, L. (2006). The complexity of finding an optimal policy for language convergence. In 9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings (pp. 804-815). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4095 LNAI). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/11840541_66

The complexity of finding an optimal policy for language convergence. / Lakkaraju, Kiran; Gasser, Les.

9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings. Springer-Verlag Berlin Heidelberg, 2006. p. 804-815 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4095 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lakkaraju, K & Gasser, L 2006, The complexity of finding an optimal policy for language convergence. in 9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4095 LNAI, Springer-Verlag Berlin Heidelberg, pp. 804-815, 9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Rome, Italy, 9/25/06. https://doi.org/10.1007/11840541_66

Lakkaraju K, Gasser L. The complexity of finding an optimal policy for language convergence. In 9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings. Springer-Verlag Berlin Heidelberg. 2006. p. 804-815. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11840541_66

Lakkaraju, Kiran ; Gasser, Les. / The complexity of finding an optimal policy for language convergence. 9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings. Springer-Verlag Berlin Heidelberg, 2006. pp. 804-815 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cfe446d1ee414fe797ce4a80a4b1981f,

title = "The complexity of finding an optimal policy for language convergence",

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

author = "Kiran Lakkaraju and Les Gasser",

year = "2006",

doi = "10.1007/11840541_66",

language = "English (US)",

isbn = "3540386084",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag Berlin Heidelberg",

pages = "804--815",

booktitle = "9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings",

note = "9th International Conference on Simulation of Adaptive Behavior, SAB 2006 ; Conference date: 25-09-2006 Through 29-09-2006",

}

TY - GEN

T1 - The complexity of finding an optimal policy for language convergence

AU - Lakkaraju, Kiran

AU - Gasser, Les

PY - 2006

Y1 - 2006

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

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

UR - http://www.scopus.com/inward/record.url?scp=33749670736&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33749670736&partnerID=8YFLogxK

U2 - 10.1007/11840541_66

DO - 10.1007/11840541_66

M3 - Conference contribution

AN - SCOPUS:33749670736

SN - 3540386084

SN - 9783540386087

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 804

EP - 815

BT - 9th International Conference on Simulation of Adaptive Behavior, SAB 2006, Proceedings

PB - Springer-Verlag Berlin Heidelberg

T2 - 9th International Conference on Simulation of Adaptive Behavior, SAB 2006

Y2 - 25 September 2006 through 29 September 2006

ER -

The complexity of finding an optimal policy for language convergence

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this