Probabilistic initial value problem for cellular automaton rule 172

Abstract : We present a method of solving of the probabilistic initial value problem for cellular automata (CA) using CA rule 172 as an example. For a disordered initial condition on an infinite lattice, we derive exact expressions for the density of ones at arbitrary time step. In order to do this, we analyze topological structure of preimage trees of finite strings of length 3. Level sets of these trees can be enumerated directly using classical combinatorial methods, yielding expressions for the number of $n$-step preimages of all strings of length 3, and, subsequently, probabilities of occurrence of these strings in a configuration obtained from the initial one after $n$ iterations of rule 172. The density of ones can be expressed in terms of Fibonacci numbers, while expressions for probabilities of other strings involve Lucas numbers. Applicability of this method to other CA rules is briefly discussed.
Type de document :
Communication dans un congrès
Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.29-40, 2010, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01185497
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 14:16:49
Dernière modification le : mardi 7 mars 2017 - 15:06:51
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:20:59

Fichier

dmAL0103.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185497, version 1

Collections

Citation

Henryk Fuks. Probabilistic initial value problem for cellular automaton rule 172. Fatès, Nazim and Kari, Jarkko and Worsch, Thomas. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, pp.29-40, 2010, DMTCS Proceedings. 〈hal-01185497〉

Partager

Métriques

Consultations de la notice

128

Téléchargements de fichiers

52