|   | 
Details
   web
Record
Author Goles, E.; Lobos, F.; Montealegre, P.; Ruivo, ELP.; de Oliveira, PPB.
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