|   | 
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 (up) UAI @ eduardo.moreno @ Serial 153
Permanent link to this record