Computational complexity of the stability problem for elementary cellular automata

Eric Goles, Fabiola Lobos, Pedro Montealegre, Eurico L.P. Ruivo, Pedro P.B. De Oliveira

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)261-304
Number of pages44
JournalJournal of Cellular Automata
Issue number4
StatePublished - 2020
Externally publishedYes


  • Computational complexity
  • Decision problem
  • Elementary cellular automata
  • One-dimensional cellular automata
  • Stability problem


Dive into the research topics of 'Computational complexity of the stability problem for elementary cellular automata'. Together they form a unique fingerprint.

Cite this