Stokastisk cellulär automat

Stokastiska cellulära automater eller probabilistiska cellulära automater (PCA) eller slumpmässiga cellulära automater eller lokalt interagerande Markov-kedjor är en viktig förlängning av cellulär automat . Cellulära automater är ett tidsdiskret dynamiskt system av interagerande enheter, vars tillstånd är diskret.

Tillståndet för samlingen av enheter uppdateras vid varje diskret tidpunkt enligt någon enkel homogen regel. Alla enheters tillstånd uppdateras parallellt eller synkront. Stokastiska cellulära automater är CA vars uppdateringsregel är en stokastisk , vilket innebär att de nya enheternas tillstånd väljs enligt vissa sannolikhetsfördelningar. Det är ett tidsdiskret slumpmässigt dynamiskt system . Från den rumsliga interaktionen mellan enheterna, trots enkelheten i uppdateringsreglerna, kan komplext beteende uppstå som självorganisering . Som matematiskt objekt kan det betraktas inom ramen för stokastiska processer som ett interagerande partikelsystem i diskret tid. Se för en mer detaljerad introduktion.

PCA som Markovs stokastiska processer

Som en diskret Markov-process definieras PCA på ett produktområde $E=\prod _{k\in G}S_{k}$ (kartesisk produkt) där $G$ är en finit eller oändlig graf, som $\mathbb {Z}$ och där $S_{k}$ är ett ändligt mellanrum, som till exempel $S_{k}=\{-1,+1\}$ eller $S_{k}=\{0,1\}$ . Övergångssannolikheten har en produktform $P(d\sigma |\eta )=\otimes _{k\in G} p_{k}(d\sigma _{k}|\eta )$ där $\eta \in E$ och $p_{k}(d\ sigma _{k}|\eta )$ är en sannolikhetsfördelning på $S_{k}$ . I allmänhet krävs en viss lokalitet ${\displaystyle p_{k}(d\sigma _{k}|\eta )=p_{k }(d\sigma _{k}|\eta _{V_{k}})} där$ η $\displaystyle \eta _{V_{k}}=(\eta _{j})_{j\in V_{k}}}$ med ${V_{k}}$ en ändlig grannskap av k. Se för en mer detaljerad introduktion efter sannolikhetsteorins synvinkel.

Exempel på stokastisk cellulär automat

Majoriteten av cellulär automat

Det finns en version av majoriteten av cellulära automater med probabilistiska uppdateringsregler. Se Tooms regel .

Relation till gitter slumpmässiga fält

PCA kan användas för att simulera Ising-modellen för ferromagnetism i statistisk mekanik . Vissa kategorier av modeller studerades ur en statistisk mekanisk synvinkel.

Cellular Potts modell

Det finns ett starkt samband mellan probabilistiska cellulära automater och den cellulära Potts-modellen i synnerhet när den implementeras parallellt.

Icke markovisk generalisering

Galves -Löcherbach-modellen är ett exempel på en generaliserad PCA med en icke-markovisk aspekt.

Vidare läsning

• Almeida, RM; Macau, EEN (2010), "Stochastic cellular automata model for wildland fire spread dynamics", 9th Brazilian Conference on Dynamics, Control and their Applications, 7–11 juni 2010 , doi : 10.1088 /1742-6596/285/1/012038 .
•   Clarke, KC; Hoppen, S. (1997), "A self-modifying cellular automaton model of historical urbanization in the San Francisco Bay area" (PDF) , Environment and Planning B: Planning and Design , 24 (2): 247–261, doi : 10.1068/b240247 , S2CID 40847078 .
• Mahajan, Meena Bhaskar (1992), Studier i språkklasser definierade av olika typer av tidsvarierande cellulära automater , Ph.D. avhandling, Indian Institute of Technology Madras .
•   Nishio, Hidenosuke; Kobuchi, Youichi (1975), "Fault tolerant cellular spaces", Journal of Computer and System Sciences , 11 (2): 150–170, doi : 10.1016/s0022-0000(75)80065-1 , MR 0389442 .
•   Smith, Alvy Ray, III (1972), "Real-time language recognition by one-dimensional cellular automata", Journal of Computer and System Sciences , 6 (3): 233–253, doi : 10.1016/S0022-0000(72) 80004-7 , MR 0309383 .
•   Louis, P.-Y.; Nardi, FR, red. (2018). Probabilistiska cellulära automater . Uppkomst, komplexitet och beräkning. Vol. 27. Springer. doi : 10.1007/978-3-319-65558-1 . hdl : 2158/1090564 . ISBN 9783319655581 .
•    Agapie, A.; Andreica, A.; Giuclea, M. (2014), "Probabilistic Cellular Automata", Journal of Computational Biology , 21 (9): 699–708, doi : 10.1089/cmb.2014.0074 , PMC 4148062 , PMID 24999557