A directed graph allowing for the exploration of the set of number-conserving non-uniform one-dimensional binary cellular automata with radius one and half

Abstract The main obstacle in the quest for non-uniform cellular automata that meet the often desired property of number conservation is the vast size of the search space, going far beyond the capabilities of today’s computers. In this paper, we expound the construction of a directed graph $$\Pi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Π</mml:mi> </mml:math> related to the set of all number-conserving non-uniform one-dimensional binary cellular automata with radius one and half (i.e., the neighborhood of a cell consists of four cells). We show that there is a one-to-one correspondence between the set of all such cellular automata on a finite grid with n cells and the set of all length- n closed directed walks in $$\Pi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Π</mml:mi> </mml:math> . This provides us with a powerful tool to investigate non-uniform cellular automata of this type.