toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author (up) Goles, E.; Moreira, A.; Rapaport, I. pdf  doi
openurl 
  Title Communication complexity in number-conserving and monotone cellular automata Type Journal Article
  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 no  
  Call Number UAI @ eduardo.moreno @ Serial 153  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: