Geodesic
Probabilistic initial value problem for cellular automaton rule 172
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS (2010).

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

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. 
@article{DMTCS_2010_special_257_a6,
     author = {Fuks, Henryk},
     title = {Probabilistic initial value problem for cellular automaton rule 172},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS},
     year = {2010},
     doi = {10.46298/dmtcs.2761},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2761/}
}
TY  - JOUR
AU  - Fuks, Henryk
TI  - Probabilistic initial value problem for cellular automaton rule 172
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2761/
DO  - 10.46298/dmtcs.2761
LA  - en
ID  - DMTCS_2010_special_257_a6
ER  - 
%0 Journal Article
%A Fuks, Henryk
%T Probabilistic initial value problem for cellular automaton rule 172
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2761/
%R 10.46298/dmtcs.2761
%G en
%F DMTCS_2010_special_257_a6
Fuks, Henryk. Probabilistic initial value problem for cellular automaton rule 172. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS (2010). doi : 10.46298/dmtcs.2761. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2761/

Cité par Sources :