en>Bearcat: /* References */fix sp of category name using AWB

2014-01-01T17:54:29Z

References: fix sp of category name using AWB

New page

{{Multiple issues|{{citation style|date=June 2013}}{{technical|date=June 2013}}}}

'''Stochastic cellular automata''' or ''''probabilistic cellular automata'''' (PCA) or ''''random cellular automata'''' or '''locally interacting [[Markov chain]]s'''<ref>Locally interacting systems and their application in Biology, Dobrushin, Kryukov, Toom editors, 1978, Lecture Notes in Math vol 653, springer pp 2–113</ref> are an important extension of [[cellular automaton]]. Cellular automata are a discrete-time [[dynamical system]] of interacting entities, whose state is discrete.

The state of the collection of entities is updated at each discrete time according to some simple homogenous rule. All entities' states are updated in parallel or synchronously. Stochastic Cellular Automata are CA whose updating rule is a stochastic one, which means the new entities' states are chosen according to some probability distributions. It is a discrete-time [[random dynamical system]]. From the spatial interaction between the entities, despite the simplicity of the updating rules, [[complex system|complex behaviour]] may [[emergence|emerge]] like [[self-organization]]. As mathematical object, it may be considered in the framework of [[stochastic processes]] as an [[interacting particle system]] in discrete-time.

Up-to-date examples of applications for CA and PCA main be found for instance there.<ref>Series: Lecture Notes in Computer Science, Vol. 7495, 6350, 5191, 4173, 3305. Ed. Springer</ref>

== PCA as Markov stochastic processes ==

As discrete-time Markov process, PCA are defined on a product space <math> E=\prod_{k \in G} S_k </math> (cartesian product) where <math> G </math>
is a finite or infinite graph, like <math> \mathbb Z </math> and where <math> S_k </math> is a finite space, like for instance
<math> S_k=\{-1,+1\} </math> or <math> S_k=\{0,1\} </math>. The transition probability has a product form
<math> P(d\sigma | \eta) = \otimes_{k \in G} p_k(d\sigma_k | \eta) </math> where
<math> \eta \in E </math> and <math> p_k(d\sigma_k | \eta) </math> is a probability distribution on <math> S_k </math>.
In general some locality is required <math> p_k(d\sigma_k | \eta)=p_k(d\sigma_k | \eta_{V_k}) </math> where
<math> \eta_{V_k}=(\eta_j)_{j\in V_k} </math> with <math> {V_k} </math> a finite neighbourhood of k.

== Examples of stochastic cellular automaton ==

=== Majority cellular automaton ===

There is a version of the [[majority problem (cellular automaton)|majority cellular automaton]] with probabilistic updating rules.

=== Relation to random fields ===
PCA may be used to simulate the [[Ising model]] of [[ferromagnetism]] in [[statistical mechanics]].<ref name="vichniac">{{citation|title=Simulating physics with cellular automata|journal=Physica D|first=G.|last=Vichniac|volume=10|year=1984|pages=96–115}}.</ref>
Some categories of models were studied from a statistical mechanics point of view.

=== Cellular Potts model ===
There is a strong connection between probabilistic cellular automata and the [[cellular Potts model]] in particular when it is implemented in parallel.

== References ==
[1] Smith Iii, A. 1972. Real-time language recognition by one-dimensional cellular automata. J. Comput. Syst. Sci. 6, 233–253.

[2] Mahajan, M. 1992. Studies in language classes defined by different types of time-varying cellular automata. Ph.D. Dissertation.

[3] Nishio, H. And Kobuchi, Y. 1975. Fault tolerant cellular spaces. J. Comput. Syst. Sci. 11, 150–170.

[4] Clarke, K. C. And Hoppen, S. 1997. A self-modifying cellular automaton model of historical urbanization in the San Francisco Bay area. Environment and Planning B: Planning and Design, Vol. 24, 247–261

[5] Almeida, R. M. And Macau, E. E. N. 2010. Stochastic cellular automata model for wildland fire spread dynamics. 9th Brazilian Conference on Dynamics, Control and their Applicarions, June 7–11, 2010.

[6] Wolfgang von der Linden And Ewald Schachinger. 2005. Computer simulation, lecture notes.

[7] Klaus Lichtenegger. 2005. Stochastic cellular automaton models in disease spreading and ecology

[8] Benny Brown. 2003. Phase transition of two-neighbor stochastic cellular automata.

[9] http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

== References cited in text ==
{{reflist}}

[[Category:Cellular automata]]
[[Category:Stochastic processes]]
[[Category:Lattice models]]
[[Category:Markov processes]]
[[Category:Self-organization]]
[[Category:Complex systems theory]]
[[Category:Spatial processes]]
[[Category:Stochastic models]]
[[Category:Markov models]]

Tree volume measurement - Revision history

en>Bearcat: /* References */fix sp of category name using AWB