Goles, E., Lobos, F., Montealegre, P., Ruivo, E. L. P., & de Oliveira, P. P. B. (2020). Computational Complexity of the Stability Problem for Elementary Cellular Automata. J. Cell. Autom., 15(4), 261–304.
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.
