Automata Networks

We define an Automata Network $\sigma$ as a structure

$$(C, A, S_0, N, \Delta),$$ (11)

where

• C is a set of cells;
• A is an alphabet of states (attributes);
• $S:\,C \rightarrow A$ is a state, $\qquad$ S₀ - an initial state;
• $N:\,C \rightarrow \cal{P}(C)$ is a neighborhood system, $\qquad$ $\cal{P}(C)$ is the power-set of C,
  $\forall c \in C: \;\; N(c)$ is the neighborhood of c;
• $\Delta:\,\Sigma \rightarrow \Sigma$ is a global dynamic rule (GDR), $\;\;\;\;$ $\Sigma = \{S\,\vert\,S \mbox{\rm ~is a state}\}$.

$$\Delta^n:\, S_{n-1} \longmapsto S_n \qquad n=1,2, \dots, M$$ (12)

The global dynamic rule $\Delta$ comes about from the local dynamic rules (LDRs)

$$\delta_c:\, \Sigma_{N(c)} \rightarrow A,$$ (13)

where S_N(c) is the restriction of S to N(c). Every LDR $\delta_c$ gives a new state value to the cell c as a function of cell states from the neighborhood N(c) of c. The action of $\Delta$

$$\Delta(S) = \bigcup_{c \in C}S[S(c) \leftarrow \delta_c(S_{N(c)})],$$ (14)

is the union of the states obtained by replacing the state of each cell c accordingly to $\delta_c$.

Automata Networks can be considered as a generalization of Cellular Automata, the main difference is our automata networks have non-regular structure of the system of the cell neighborhoods. There is no a common template of vicinity for cells, the neighborhoods of cells have variable cardinality and, hence, the LDRs have variable arity. There are possible cases when $c \notin N(c)$ and even $N(c) =\{\emptyset\}$.

An automata network $\sigma$ works as follows. If an initial state S₀ is given, it iteratively applies the GDR $\Delta$ until it reaches a steady attractive state S_A:

$$S_0 \stackrel{\Delta}{\longrightarrow} S_1 \stackrel{\Delta}... ...longrightarrow} \dots \stackrel{\Delta}{\longrightarrow} S_A.$$

The cells work synchronously in parallel governed by some global synchronization signals.