|   | 
Author Goles, E.; Guillon, P.; Rapaport, I.
Title Traced communication complexity of cellular automata Type
Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 412 Issue 30 Pages 3906-3916
Keywords Cellular automata; Communication complexity
Abstract 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.
Address [Guillon, P; Rapaport, I] Univ Chile, DIM CMM, CNRS, UMI 2807, Santiago, Chile, Email: eric.chacc@uai.cl
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0304-3975 ISBN (down) Medium
Area Expedition Conference
Notes WOS:000292589800009 Approved
Call Number UAI @ eduardo.moreno @ Serial 152
Permanent link to this record