| Records |
| 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 |
| |
|
| |
| Author |
Goles, E.; Moreira, A. |
| Title |
Number-Conserving Cellular Automata and Communication Complexity: A Numerical Exploration Beyond Elementary CAs |
Type |
|
| Year |
2012 |
Publication |
Journal Of Cellular Automata |
Abbreviated Journal |
J. Cell. Autom. |
| Volume |
7 |
Issue |
2 |
Pages |
151-165 |
| Keywords |
Number-Conserving; Communication Complexity; One-dimensional Cellular Automata |
| Abstract |
We perform a numerical exploration of number-conserving cellular automata (NCCA) beyond the class of elementary CAs, in search of examples with high communication complexity. We consider some possible generalizations of the elementary rule 184 (a minimal model of traffic, which is the only non-trivial elementary NCCA). as well as the classes of NCCAs which minimally extend either the radius or the state set (with respect to the 2 states and radius 1 of the elementary case). Both for 3 states and radius 1, and for 2 stales and radius 2, NCCA appear that are conjectured to have maximal (exponential) communication complexity. Examples are given also for (conjectured) linear and quadratic behaviour. |
| Address |
[Goles, Eric] Univ Adolfo Ibanez, Santiago, Chile, Email: andres.moreira@usm.cl |
| Corporate Author |
|
Thesis |
|
| Publisher |
Old City Publishing Inc |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
1557-5969 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000302978700004 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
210 |
| Permanent link to this record |
