toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author (up) 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.  
  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
Select All    Deselect All
 |   | 

Save Citations:
Export Records: