TY - JOUR
T1 - Computational complexity of the stability problem for elementary cellular automata
AU - Goles, Eric
AU - Lobos, Fabiola
AU - Montealegre, Pedro
AU - Ruivo, Eurico L.P.
AU - De Oliveira, Pedro P.B.
N1 - Publisher Copyright:
© 2020 Old City Publishing, Inc.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Computational complexity
KW - Decision problem
KW - Elementary cellular automata
KW - One-dimensional cellular automata
KW - Stability problem
UR - http://www.scopus.com/inward/record.url?scp=85092943279&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:85092943279
SN - 1557-5969
VL - 15
SP - 261
EP - 304
JO - Journal of Cellular Automata
JF - Journal of Cellular Automata
IS - 4
ER -