Cellular Automaton Performing Two-Coloring of Square Tiled Planes

Jiri Kroc
University of West Bohemia
Helsinki School of Economics

The main goal of this work is to show on a simple periodic case—and easy to simulate—that there exists a class of cellular automata, possibly deterministic, enabling us to effectively perform the coloring of tiled planes. Similar algorithms—where determinism is in question—could be applied to the three-neighbor case on square grids and to aperiodic or quasiperiodic three-neighbor tilings, and for example, the Penrose tiling.

A rule which performs a coloring of tiles ensures that no two neighboring tiles have the same color. A 2D deterministic cellular automaton is defined and performs a two-coloring of squares in the plane using self-organization.

Anti-phase separation boundaries lie between two regions, inside of which all tiles are correctly colored with respect to each other, but the boundary itself is out of the order. They naturally emerge from random and non-random initial conditions, and their presence could lead to more than two times longer the total simulation time.

Appearance of such anti-phase separation borders could be protected by use of a special initial condition consisting of one seed—located in the left-lower corner in our case. Seed has one color and is immersed into the homogeneous ‘sea’ of cells having the opposite color. This initial condition is in the perfect consistence with the rule. One has to keep in mind that both the rule and initial condition are equally important in order to get an effective, correct, and fast solution.

Created by Mathematica  (April 20, 2004)