Cellular Automata/Global Dynamics

Attractor BasinEdit

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

Graphic conventionsEdit


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 bijectivityEdit

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

Injectivity of the global transition functionEdit

  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 functionEdit

  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 functionEdit

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