On the analysis of ''simple'' 2D stochastic cellular automata
Cellular automata are usually associated with synchronous deterministic dynamics, and their asynchronous or stochastic versions have been far less studied although significant for modeling purposes. This paper analyzes the dynamics of a two-dimensional cellular automaton, 2D Minority, for the Moore...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2010-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/518/pdf |
| _version_ | 1797270161270505472 |
|---|---|
| author | Damien Regnault Nicolas Schabanel Eric Thierry |
| author_facet | Damien Regnault Nicolas Schabanel Eric Thierry |
| author_sort | Damien Regnault |
| collection | DOAJ |
| description | Cellular automata are usually associated with synchronous deterministic dynamics, and their asynchronous or stochastic versions have been far less studied although significant for modeling purposes. This paper analyzes the dynamics of a two-dimensional cellular automaton, 2D Minority, for the Moore neighborhood (eight closest neighbors of each cell) under fully asynchronous dynamics (where one single random cell updates at each time step). 2D Minority may appear as a simple rule, but It is known from the experience of Ising models and Hopfield nets that 2D models with negative feedback are hard to study. This automaton actually presents a rich variety of behaviors, even more complex that what has been observed and analyzed in a previous work on 2D Minority for the von Neumann neighborhood (four neighbors to each cell) (2007) This paper confirms the relevance of the later approach (definition of energy functions and identification of competing regions) Switching to the Moot e neighborhood however strongly complicates the description of intermediate configurations. New phenomena appear (particles, wider range of stable configurations) Nevertheless our methods allow to analyze different stages of the dynamics It suggests that predicting the behavior of this automaton although difficult is possible, opening the way to the analysis of the whole class of totalistic automata |
| first_indexed | 2024-04-25T01:59:52Z |
| format | Article |
| id | doaj.art-b0ba88b3c16040a38da466410d897c39 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:59:52Z |
| publishDate | 2010-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-b0ba88b3c16040a38da466410d897c392024-03-07T15:15:53ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502010-01-01Vol. 12 no. 210.46298/dmtcs.518518On the analysis of ''simple'' 2D stochastic cellular automataDamien Regnault0https://orcid.org/0000-0001-9815-5606Nicolas Schabanel1Eric Thierry2Laboratoire de l'Informatique du ParallélismeInstitut Rhône-Alpin des systèmes complexesInstitut Rhône-Alpin des systèmes complexesCellular automata are usually associated with synchronous deterministic dynamics, and their asynchronous or stochastic versions have been far less studied although significant for modeling purposes. This paper analyzes the dynamics of a two-dimensional cellular automaton, 2D Minority, for the Moore neighborhood (eight closest neighbors of each cell) under fully asynchronous dynamics (where one single random cell updates at each time step). 2D Minority may appear as a simple rule, but It is known from the experience of Ising models and Hopfield nets that 2D models with negative feedback are hard to study. This automaton actually presents a rich variety of behaviors, even more complex that what has been observed and analyzed in a previous work on 2D Minority for the von Neumann neighborhood (four neighbors to each cell) (2007) This paper confirms the relevance of the later approach (definition of energy functions and identification of competing regions) Switching to the Moot e neighborhood however strongly complicates the description of intermediate configurations. New phenomena appear (particles, wider range of stable configurations) Nevertheless our methods allow to analyze different stages of the dynamics It suggests that predicting the behavior of this automaton although difficult is possible, opening the way to the analysis of the whole class of totalistic automatahttps://dmtcs.episciences.org/518/pdfstochastic cellular automatacomplex systems[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Damien Regnault Nicolas Schabanel Eric Thierry On the analysis of ''simple'' 2D stochastic cellular automata Discrete Mathematics & Theoretical Computer Science stochastic cellular automata complex systems [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | On the analysis of ''simple'' 2D stochastic cellular automata |
| title_full | On the analysis of ''simple'' 2D stochastic cellular automata |
| title_fullStr | On the analysis of ''simple'' 2D stochastic cellular automata |
| title_full_unstemmed | On the analysis of ''simple'' 2D stochastic cellular automata |
| title_short | On the analysis of ''simple'' 2D stochastic cellular automata |
| title_sort | on the analysis of simple 2d stochastic cellular automata |
| topic | stochastic cellular automata complex systems [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/518/pdf |
| work_keys_str_mv | AT damienregnault ontheanalysisofsimple2dstochasticcellularautomata AT nicolasschabanel ontheanalysisofsimple2dstochasticcellularautomata AT ericthierry ontheanalysisofsimple2dstochasticcellularautomata |