Cellular Automata/Global Dynamics

Attractor Basin

When discussing global dynamics of cellular automata the word state is used to describe configurations.

Graphic conventions

The following diagrams/captions are based on the original figure State-space and basins of attraction on the DDLab website. Sub-trees, basins of attraction, and the entire basin of attraction field (for cellular automata, random Boolean networks, and discrete dynamic networks in general) can be computed and drawn with the DDLab software.

The state space is made of all available states of a cellular automaton. It's size is $S = v^{n}$ where $n$ is the the size of the (finite) lattice, and $v$ is the value-range or alphabet, $v=2$ for binary systems. $B$ is one of the states.

The trajectory $A \rightarrow B \rightarrow C$ is defined by the global transition function. State $A$ is a predecessor and state $C$ is the successor of state $B$.

If the global transtition function is not injective, than states may have more than one predecessor (preimage). The in-degree of the state $B$ is the number of its predecessors. A state may have no predecessors, than it is called garden of Eden.

A trajectory may encounter a state occurred previously (it must if the lattice is finite), thus it has entered an attraction cycle. A point attraction cycle has the length of a single cell.

By recursively searching predecessors from a root state on the attraction cycle (the predecessor on the cycle is excluded) till all garden of Eden states are reached a transient tree is constructed. A subtree can be constructed from an arbitrary state on the tree, the root of the subtree.

By adding transient trees to each state on the attraction cycle, a basin of attraction is constructed. Some attraction cycles may have no transient trees, this is especially true for reversible cellular automata.

By grouping all the states in the state space into respective basins of attraction, a basin of attraction field is constructed.

Injectivity, surjectivity and bijectivity

The CA rule is reversible, if the global transition function $F$ is bijective (both injective and surjective).

Injectivity of the global transition function

$F$ is injective, there is at most one preimage for any CA configuration.

$F: X \mapsto Y \qquad \forall x_1,x_2 \in \Omega \; [x_1 \neq x_2 \Rightarrow F(x_1) \neq F(x_2)]$

So there are no configurations with more than one predecessor.

Surjectivity of the global transition function

$F$ is injective, there is at least one preimage for any CA configuration.

$F: X \mapsto Y \qquad \forall y \in \Omega \; \exists x [ y = F(x)]$

So there are no configurations without a predecessor (so called Garden of Eden).

It is easy to determine the existence of garden of Eden states for one dimensional CA using De Bruijn Diagrams.

Bijectivity of the global transition function

$F$ is bijective if it is both injective and surjective. For any configuration there is exactly one predecessor.