Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority

DOI10.1007/978-3-540-74456-6_30MaRDI QIDQ3525580zbMATH OpenOpenAlexFDO

Authors Damien Regnault, Nicolas Schabanel, Eric Thierry

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0706.2479

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Abstract: Cellular automata are often used to model systems in physics, social sciences, biology that are inherently asynchronous. Over the past 20 years, studies have demonstrated that the behavior of cellular automata drastically changed under asynchronous updates. Still, the few mathematical analyses of asynchronism focus on one-dimensional probabilistic cellular automata, either on single examples or on specific classes. As for other classic dynamical systems in physics, extending known methods from one- to two-dimensional systems is a long lasting challenging problem. In this paper, we address the problem of analysing an apparently simple 2D asynchronous cellular automaton: 2D Minority where each cell, when fired, updates to the minority state of its neighborhood. Our experiments reveal that in spite of its simplicity, the minority rule exhibits a quite complex response to asynchronism. By focusing on the fully asynchronous regime, we are however able to describe completely the asymptotic behavior of this dynamics as long as the initial configuration satisfies some natural constraints. Besides these technical results, we have strong reasons to believe that our techniques relying on defining an energy function from the transition table of the automaton may be extended to the wider class of threshold automata.

Recommendations

• Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority
• scientific article; zbMATH DE number 5761854
• On the Analysis of “Simple” 2D Stochastic Cellular Automata
• Quick Energy Drop in Stochastic 2D Minority
• Stochastic minority on graphs

Cited in

(11)

• Quick Energy Drop in Stochastic 2D Minority
• Stochastic minority on graphs
• Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority
• Examples of fast and slow convergence of 2D asynchronous cellular systems
• Stabilization Time in Weighted Minority Processes
• A Study on the Automatic Generation of Asynchronous Cellular Automata Rules by Means of Genetic Algorithms
• Boundary conditions and phase transitions in neural networks. Theoretical results
• scientific article; zbMATH DE number 5761854 (Why is no real title available?)
• On the Analysis of “Simple” 2D Stochastic Cellular Automata
• A study on learning robustness using asynchronous 1D cellular automata rules
• Directed Percolation Arising in Stochastic Cellular Automata Analysis

This page was built for publication: Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3525580)