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.
| Original language | English |
|---|---|
| Pages (from-to) | 261-304 |
| Number of pages | 44 |
| Journal | Journal of Cellular Automata |
| Volume | 15 |
| Issue number | 4 |
| State | Published - 2020 |
| Externally published | Yes |
Keywords
- Computational complexity
- Decision problem
- Elementary cellular automata
- One-dimensional cellular automata
- Stability problem