Geodesic
Freezing, Bounded-Change and Convergent Cellular Automata
Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1.

Voir la notice de l'article provenant de la source Episciences

This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-K\r{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from convergent cellular automata in dimension~1, but also dimension~1 versus higher dimensions for freezing cellular automata. Another surprising dimension-sensitive result obtained is that nilpotency becomes decidable in dimension~ 1 for all the three classes, while it stays undecidable even for freezing cellular automata in higher dimension.
DOI : 10.46298/dmtcs.5734
Classification : 68Q25, 68Q80 
@article{DMTCS_2022_24_1_a2,
     author = {Ollinger, Nicolas and Theyssier, Guillaume},
     title = {Freezing, {Bounded-Change} and {Convergent} {Cellular} {Automata}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2022},
     doi = {10.46298/dmtcs.5734},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5734/}
}
TY  - JOUR
AU  - Ollinger, Nicolas
AU  - Theyssier, Guillaume
TI  - Freezing, Bounded-Change and Convergent Cellular Automata
JO  - Discrete mathematics & theoretical computer science
PY  - 2022
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5734/
DO  - 10.46298/dmtcs.5734
LA  - en
ID  - DMTCS_2022_24_1_a2
ER  - 
%0 Journal Article
%A Ollinger, Nicolas
%A Theyssier, Guillaume
%T Freezing, Bounded-Change and Convergent Cellular Automata
%J Discrete mathematics & theoretical computer science
%D 2022
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5734/
%R 10.46298/dmtcs.5734
%G en
%F DMTCS_2022_24_1_a2
Ollinger, Nicolas; Theyssier, Guillaume. Freezing, Bounded-Change and Convergent Cellular Automata. Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1. doi : 10.46298/dmtcs.5734. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5734/

Cité par Sources :