| Record |
| 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 |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000292589800009 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
152 |
| Permanent link to this record |
