Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Color War: Cellular Automata with Majority-Rule
verfasst von : Bernd Gärtner, Ahad N. Zehmakan
Erschienen in: Language and Automata Theory and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Consider a graph \(G=(V,E)\) and a random initial vertex-coloring such that each vertex is blue independently with probability \(p_{b}\le 1/2\), and red otherwise. In each step, all vertices change their current color synchronously to the most frequent color in their neighborhood (in the case of a tie, a vertex conserves its current color). We are interested in the behavior of this very natural process, especially in 2-dimensional grids and tori (cellular automata with majority rule). In the present paper, as a main result we prove that a grid \(G_{n,n}\) or a torus \(T_{n,n}\) with 4-neighborhood (8-neighborhood) exhibits a threshold behavior: with high probability, it reaches a red monochromatic configuration in a constant number of steps if \(p_b\ll n^{-\frac{1}{2}}\) (\(p_b\ll n^{-\frac{1}{6}}\)), but \(p_b\gg n^{-\frac{1}{2}}\) (\(p_b\gg n^{-\frac{1}{6}}\)) results in a bichromatic period of configurations of length one or two, after at most \(2n^2\) (\(4n^2\)) steps with high probability.