JCA Home • Issue Contents

Computational Complexity of the Stability Problem for Elementary Cellular Automata
Eric Goles, Fabiola Lobos, Pedro Montealegre, Eurico L.P. Ruivo and Pedro P.B. De Oliveira

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.

Keywords: One-dimensional cellular automata, elementary cellular automata, computational complexity, stability problem, decision problem

Full Text (IP)