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

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	461-496
Number of pages	36
Journal	International Journal of Game Theory
Volume	45
Issue number	1-2
DOIs	https://doi.org/10.1007/s00182-015-0521-7
Publication status	Published - 1 Mar 2016

Keywords

Automata
Bounded memory
Complexity
De Bruijn sequences

Access to Document

10.1007/s00182-015-0521-7

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this