The complexity of interacting automata

The complexity of interacting automata — International Journal of Game Theory, 45:461-496, 2016
Authors

Olivier Gossner

Penélope Hernández

and Ron Peretz

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 m log m. We investigate implications of these results on the correlated min–max value of repeated games played by automata.

← All research

International Journal of Game Theory, 45(1–2), 461–496 (2016)

Paper PDF

Citation

BibTeX citation:
@article{gossner2016,
  author = {Gossner, Olivier and Hernández, Penélope and Ron Peretz,
    and},
  title = {The Complexity of Interacting Automata},
  journal = {International Journal of Game Theory},
  volume = {45},
  number = {1-2},
  pages = {461-496},
  date = {2016},
  url = {https://gossner.me/papers/the-complexity-of-interacting-automata.html},
  langid = {en},
  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 m log m. We
    investigate implications of these results on the correlated min–max
    value of repeated games played by automata.}
}
For attribution, please cite this work as:
Gossner, Olivier, Penélope Hernández, and and Ron Peretz. 2016. “The Complexity of Interacting Automata.” International Journal of Game Theory 45 (1-2): 461–96. https://gossner.me/papers/the-complexity-of-interacting-automata.html.