Traced communication complexity of cellular automata
Goles
E
author
Guillon
P
author
Rapaport
I
author
2011
English
We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata. (C) 2011 Elsevier B.V. All rights reserved.
Cellular automata
Communication complexity
WOS:000292589800009
exported from refbase (show.php?record=152), last updated on Thu, 04 Aug 2011 15:36:46 -0400
text
files/104_Goles_etal2011.pdf
10.1016/j.tcs.2011.02.025
Goles_etal2011
Theoretical Computer Science
Theor. Comput. Sci.
2011
Elsevier Science Bv
continuing
periodical
academic journal
412
30
3906
3916
0304-3975