# Cellular Automata/Global Dynamics

## Attractor Basin[edit | edit source]

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

### Graphic conventions[edit | edit source]

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 where is the size of the (finite) lattice,
and is the value-range or alphabet, for binary systems.
is one of the states.

The *trajectory* is defined by the global transition function. State is a *predecessor* and state is the *successor* of state .

If the global transtition function is not injective, than states may have more than one predecessor (preimage). The *in-degree* of the state 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[edit | edit source]

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

### Injectivity of the global transition function[edit | edit source]

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

So there are no configurations with more than one predecessor.

### Surjectivity of the global transition function[edit | edit source]

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

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[edit | edit source]

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