Computational Complexity of the Stability Problem for Elementary Cellular Automata
Goles
E
author
Lobos
F
author
Montealegre
P
author
Ruivo
E
L
P
author
de Oliveira
P
P
B
author
2020
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.
One-dimensional cellular automata
elementary cellular automata
computational complexity
stability problem
decision problem
WOS:000613086900002
exported from refbase (show.php?record=1329), last updated on Thu, 25 Feb 2021 16:29:18 -0300
text
Goles_etal2020
Journal of Cellular Automata
J. Cell. Autom.
2020
continuing
periodical
academic journal
15
4
261
304
1557-5969