|   | 
Details
   web
Records
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
 

 
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
 

 
Author Goles, E.; Meunier, P.E.; Rapaport, I.; Theyssier, G.
Title Communication complexity and intrinsic universality in cellular automata Type
Year 2011 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.
Volume 412 Issue 1-2 Pages 2-21
Keywords Cellular automata; Communication complexity; Intrinsic universality
Abstract The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains hard in most cases. In this article, we introduce necessary conditions for a cellular automaton to be “universal”, according to a precise notion of simulation, related both to the dynamics of cellular automata and to their computational power. This notion of simulation relies on simple operations of space-time rescaling and it is intrinsic to the model of cellular automata. intrinsic universality, the derived notion, is stronger than Turing universality, but more uniform, and easier to define and study. Our approach builds upon the notion of communication complexity, which was primarily designed to study parallel programs, and thus is, as we show in this article, particulary well suited to the study of cellular automata: it allowed us to show, by studying natural problems on the dynamics of cellular automata, that several classes of cellular automata, as well as many natural (elementary) examples, were not intrinsically universal. (C) 2010 Elsevier B.V. All rights reserved.
Address [Meunier, P. -E.; Theyssier, G.] Univ Savoie, CNRS, LAMA, F-73376 Le Bourget Du Lac, France, Email: guillaume.theyssier@univ-savoie.fr
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:000285952400002 Approved
Call Number UAI @ eduardo.moreno @ Serial 118
Permanent link to this 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