The complexity of interacting automata

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.