Skip to content

The complexity of interacting automata

    Olivier Gossner, Penelope Hernández, and Ron Peretz
    International Journal of Game Theory, 45:461-496, 2016

    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.

    Interacting automata