The complexity of interacting automata

Olivier Gossner; Penélope Hernández; Ron Peretz

doi:10.1007/s00182-015-0521-7

The complexity of interacting automata

Olivier Gossner
, Penélope Hernández
, Ron Peretz

School of Economics
University of Valencia
Bar-Ilan University

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

This paper studies the interaction of automata of size m. We characterise statistical properties satisfied by random plays generated by a correlated pair of automata with m states each. We show that in some respect the pair of automata can be identified with a more complex automaton of size comparable to (Formula presented.). We investigate implications of these results on the correlated min–max value of repeated games played by automata.

langue originale	Anglais
Pages (de - à)	461-496
Nombre de pages	36
journal	International Journal of Game Theory
Volume	45
Numéro de publication	1-2
Les DOIs	https://doi.org/10.1007/s00182-015-0521-7
état	Publié - 1 mars 2016

Accès au document

10.1007/s00182-015-0521-7

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@article{894818265d124251ac0ec9fe17eebfb0,

title = "The complexity of interacting automata",

abstract = "This paper studies the interaction of automata of size m. We characterise statistical properties satisfied by random plays generated by a correlated pair of automata with m states each. We show that in some respect the pair of automata can be identified with a more complex automaton of size comparable to (Formula presented.). We investigate implications of these results on the correlated min–max value of repeated games played by automata.",

keywords = "Automata, Bounded memory, Complexity, De Bruijn sequences",

author = "Olivier Gossner and Pen{\'e}lope Hern{\'a}ndez and Ron Peretz",

note = "Publisher Copyright: {\textcopyright} 2015, Springer-Verlag Berlin Heidelberg.",

year = "2016",

month = mar,

day = "1",

doi = "10.1007/s00182-015-0521-7",

language = "English",

volume = "45",

pages = "461--496",

journal = "International Journal of Game Theory",

issn = "0020-7276",

number = "1-2",

}

TY - JOUR

T1 - The complexity of interacting automata

AU - Gossner, Olivier

AU - Hernández, Penélope

AU - Peretz, Ron

PY - 2016/3/1

Y1 - 2016/3/1

N2 - This paper studies the interaction of automata of size m. We characterise statistical properties satisfied by random plays generated by a correlated pair of automata with m states each. We show that in some respect the pair of automata can be identified with a more complex automaton of size comparable to (Formula presented.). We investigate implications of these results on the correlated min–max value of repeated games played by automata.

AB - This paper studies the interaction of automata of size m. We characterise statistical properties satisfied by random plays generated by a correlated pair of automata with m states each. We show that in some respect the pair of automata can be identified with a more complex automaton of size comparable to (Formula presented.). We investigate implications of these results on the correlated min–max value of repeated games played by automata.

KW - Automata

KW - Bounded memory

KW - Complexity

KW - De Bruijn sequences

UR - https://www.scopus.com/pages/publications/84949507062

U2 - 10.1007/s00182-015-0521-7

DO - 10.1007/s00182-015-0521-7

M3 - Article

AN - SCOPUS:84949507062

SN - 0020-7276

VL - 45

SP - 461

EP - 496

JO - International Journal of Game Theory

JF - International Journal of Game Theory

IS - 1-2

ER -

The complexity of interacting automata

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation