The complexity of interacting automata

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

Olivier Gossner

Penelope 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:461-496, 2016

Paper PDF

Citation

BibTeX citation:
@article{gossner2016,
  author = {Gossner, Olivier and Hernández, Penelope and Ron Peretz,
    and},
  title = {The Complexity of Interacting Automata},
  journal = {International Journal of Game Theory},
  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, Penelope Hernández, and and Ron Peretz. 2016. “The Complexity of Interacting Automata.” International Journal of Game Theory. https://gossner.me/papers/the-complexity-of-interacting-automata.html.