toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
Author Goles, E.; Lobos, F.; Montealegre, P.; Ruivo, ELP.; de Oliveira, PPB. openurl 
  Title Computational Complexity of the Stability Problem for Elementary Cellular Automata Type
  Year 2020 Publication Journal of Cellular Automata Abbreviated Journal J. Cell. Autom.  
  Volume 15 Issue 4 Pages 261-304  
  Keywords One-dimensional cellular automata; elementary cellular automata; computational complexity; stability problem; decision problem  
  Abstract Given an elementary cellular automaton and a cell v, we define the stability decision problem as the determination of whether or not the state of cell v will ever change, at least once, during the time evolution of the rule, over a finite input configuration. Here, we perform the study of the entire elementary cellular automata rule space, for the two possible decision cases of the problem, namely, changes in v from state 0 to 1 (0 -> 1), and the other way round (1 -> 0). Out of the 256 elementary cellular automata, we show that for all of them, at least one of the two decision problems is in the NC complexity class.  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language 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:000613086900002 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1329  
Permanent link to this record
 

 
Author Goles, E.; Montalva-Medel, M.; MacLean, S.; Mortveit, H. url  openurl
  Title Block Invariance in a Family of Elementary Cellular Automata Type
  Year 2018 Publication Journal Of Cellular Automata Abbreviated Journal J. Cell. Autom.  
  Volume 13 Issue 1-2 Pages 15-32  
  Keywords Elementary cellular automata; block updates; periodic configurations; block invariance  
  Abstract We study the steady state invariance of elementary cellular automata (ECA) under different deterministic updating schemes. Specifically, we study a family of eleven ECA whose steady state invariance were left under conjecture in [2].  
  Address [Goles, Eric; Montalva-Medel, Marco; MacLean, Stephanie] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.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:000410888100002 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 782  
Permanent link to this record
 

 
Author Goles, E.; Montalva-Medel, M.; Mortveit, H.; Ramirez-Flandes, S. url  openurl
  Title Block Invariance in Elementary Cellular Automata Type
  Year 2015 Publication Journal Of Cellular Automata Abbreviated Journal J. Cell. Autom.  
  Volume 10 Issue 1-2 Pages 119-135  
  Keywords Elementary cellular automata; block updates; periodic points; block invariance  
  Abstract Consider an elementary cellular automaton (ECA) under periodic boundary conditions. Given an arbitrary partition of the set of vertices we consider the block updating, i.e. the automaton's local function is applied from the first to the last set of the partition such that vertices belonging to the same set are updated synchronously. The automaton is said block-invariant if the set of periodic configurations is independent of the choice of the block updating. When the sets of the partition are singletons we have the sequential updating: vertices are updated one by one following a permutation pi. In [5] the authors analyzed the pi-invariance of the 2(8) = 256 possible ECA rules (or the 88 non-redundant rules subset). Their main result was that for all n > 3, exactly 41 of these non-redundant rules are pi-invariant. In this paper we determine the subset of these 41 rules that are block invariant. More precisely, for all n > 3, exactly 15 of these rules are block invariant. Moreover, we deduce that block invariance also implies that the attractor structure itself is independent of the choice of the block update.  
  Address [Goles, Eric; Montalva-Medel, Marco; Ramirez-Flandes, Salvador] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Penalolen, Chile, Email: eric.chacc@uai.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:000350183000006 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 461  
Permanent link to this record
 

 
Author Goles, E.; Moreira, A.; Rapaport, I. pdf  doi
openurl 
  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 Perrot, K.; Montalva-Medel, M.; de Oliveira, P.P.B.; Ruivo, E.L.P. doi  openurl
  Title Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations Type
  Year 2020 Publication Natural Computing Abbreviated Journal Nat. Comput.  
  Volume 19 Issue 1 Pages 51-90  
  Keywords Synchronism sensitivity; Elementary cellular automata; Update digraph  
  Abstract This work is a thoughtful extension of the ideas sketched in Montalva et al. (AUTOMATA 2017 exploratory papers proceedings, 2017), aiming at classifying elementary cellular automata (ECA) according to their maximal one-step sensitivity to changes in the schedule of cells update. It provides a complete classification of the ECA rule space for all period sizes n[ 9 and, together with the classification for all period sizes n <= 9 presented in Montalva et al. (Chaos Solitons Fractals 113:209-220, 2018), closes this problem and opens further questionings. Most of the 256 ECA rule's sensitivity is proved or disproved to be maximum thanks to an automatic application of basic methods. We formalize meticulous case disjunctions that lead to the results, and patch failing cases for some rules with simple arguments. This gives new insights on the dynamics of ECA rules depending on the proof method employed, as for the last rules 45 and 105 requiring o0011THORN induction patterns.  
  Address [Perrot, Kevin] Univ, Aix Marseille Univ.,Toulon,CNRS,UMR 7020, Marseille, France, Email: kevin.perrot@lis-lab.fr  
  Corporate Author Thesis  
  Publisher Springer Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 1567-7818 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000517129300006 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 1162  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: