| Record |
| Author |
Goles, E.; Moreira, A.; Rapaport, I. |
| Title |
Communication complexity in number-conserving and monotone cellular automata |
Type |
|
| Year |
2011 |
Publication |
Theoretical Computer Science |
Abbreviated Journal |
Theor. Comput. Sci. |
| Volume |
412 |
Issue |
29 |
Pages |
3616-3628 |
| Keywords |
Cellular automata; Communication complexity; Elementary cellular automata; Number-conserving |
| Abstract |
One third of the elementary cellular automata (CAs) are either number-conserving (NCCAs) or monotone (increasing or decreasing). In this paper we prove that, for all of them, we can find linear or constant communication protocols for the prediction problem. In other words, we are able to give a succinct description for their dynamics. This is not necessarily true for general NCCAs. In fact, we also show how to explicitly construct, from any CA, a new NCCA which preserves the original communication complexity. (C) 2011 Elsevier B.V. All rights reserved. |
| Address |
[Moreira, A] Univ Tecn Federico Santa Maria, Dept Informat, Valparaiso, 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:000292077200019 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
153 |
| Permanent link to this record |
