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 - Funding Information:
This work has been partially supported by CONICYT, via PAI + Con-vocatoria Nacional Subvención a la Incorporación en la Academia Año 2017 + PAI77170068 (P.M.) and ECOS-CONICYT C16E01 (EG, FL). PPBO also thanks the Brazilian agencies CAPES (Coordenac¸ão de Aperfeic¸oamento de Pessoal de Nível Superior) and CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico), the former for the projects STIC-AmSud (CoDANet) no. 88881.197456/2018-01 and Mackenzie-PrInt no. 88887.310281/2018-00, and the latter for the research grant PQ 305199/2019-6.
Funding Information:
This work has been partially supported by CONICYT, via PAI + Convocatoria Nacional Subvencion a la Incorporacion en la Academia A?o 2017 + PAI77170068 (P.M.) and ECOS-CONICYT C16E01 (EG, FL). PPBO also thanks the Brazilian agencies CAPES (Coordena??o de Aperfei?oamento de Pessoal de Nivel Superior) and CNPq (Conselho Nacional de Desenvolvimento Cientifico e Tecnologico), the former for the projects STIC-AmSud (CoDANet) no. 88881.197456/2018-01 and Mackenzie-PrInt no. 88887.310281/2018-00, and the latter for the research grant PQ 305199/2019-6.
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 -