Complex Systems

The Time Evolution of a Greenberg–Hastings Cellular Automaton on a Finite Graph Download PDF

Nobutaka Doba
Gastroenterological Center
Yokohama City University Medical Center
4-57 Urafune-cho, Minami-ku, Yokohama, Kanagawa 232-0024, Japan


The Greenberg–Hastings cellular automaton (GHCA) is a probabilistic two-dimensional cellular automaton with a Moore or von Neumann neighborhood to mimic pattern formations of excitable media. It is also defined on a graph, where a vertex corresponds to a cell and its adjacent vertices to the neighborhood of the cell. In this paper, we study a three-valued GHCA on an arbitrary finite connected graph analytically, though it has been mainly investigated numerically. We prove that “maximum cycle density” completely decides asymptotic behavior of its time evolution.

Keywords: Greenberg–Hastings cellular automaton; graph cellular automaton