Propagation, Diffusion and Randomization in Cellular Automata

Abstract : A large part of the study of cellular automata dynamics consists in comparing pairs of configurations and their orbits. Here we focus on pairs of configurations having a finite number of differences (diamonds) like in the celebrated Garden-of-Eden theorem. First, we show that it allows to study expansive-like phenomena where classical notions of chaotic behavior like positive expansivity or strong transitivity don’t apply (in reversible CAs for instance). Second, we establish that for a large class of linear CA, diffusion of diamonds is equivalent to randomization (a large class of probability measures converge weakly towards the uniform measure under the action of the CA). Both properties are also equivalent to the absence of gliders in the CA. Finally, we give examples of reversible linear CAs that are strong randomizers (the convergence towards the uniform measure is simple and not only in Cesaro mean). This strong behavior is however provably impossible with linear CA having commuting coefficients (e.g. linear CA over cyclic groups).
Type de document :
Communication dans un congrès
Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. Lecture Notes in Computer Science, LNCS-9664, pp.3-9, 2016, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_1〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01435029
Contributeur : Hal Ifip <>
Soumis le : vendredi 13 janvier 2017 - 15:23:56
Dernière modification le : jeudi 18 janvier 2018 - 01:32:55
Document(s) archivé(s) le : vendredi 14 avril 2017 - 20:57:32

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Guillaume Theyssier. Propagation, Diffusion and Randomization in Cellular Automata. Matthew Cook; Turlough Neary. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. Lecture Notes in Computer Science, LNCS-9664, pp.3-9, 2016, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-39300-1_1〉. 〈hal-01435029〉

Partager

Métriques

Consultations de la notice

148