# Cellular Automata/Counting Preimages

Preimages are configurations in the past that lead in one step to the present configuration.

## Reversing the direction of time

Preimages of the present configuration depend on the inverse of the global transition function

The local transition function and the global transition function define the evolution of cellular automata in the forward time direction. To calculate preimages from the present configuration, inverses of the forward mappings must be defined.

The preimages of a single cell ${\displaystyle c_{x}^{t}}$ are the locally valid neighborhoods ${\displaystyle n_{x}^{t-1}}$ defined by the inverse of the local transition function

${\displaystyle f^{-1}(c_{x}^{t})=\{n_{x}^{t-1}\in S^{N}\;|\;f(n_{x}^{t-1})=c_{x}^{t}\}}$

Preimages ${\displaystyle C^{t-1}}$ of a configuration ${\displaystyle C^{t}}$ are defined by the inverse of the global transition function

${\displaystyle F^{-1}(C^{t})=\{C^{t-1}\in S^{Z}\;|\;f(C^{t-1})=C^{t}\}}$

Locally valid neighborhoods of adjacent cells must overlap correctly to become globally valid. De Bruijn diagrams describe how sequences can overlap an thus provide a method to calculate global inverses knowing the local inverse.

The number ${\displaystyle p}$ of preimages ${\displaystyle C^{t-1}}$ can vary from none to many, depending on the rule and the present configuration ${\displaystyle C^{t}}$, arising questions about the injectivity, surjectivity and reversibility of the rule.

## De Bruijn diagrams

The De Bruijn diagram

De Bruijn diagrams come from the theory describing shift registers. Its nodes are strings ${\displaystyle w}$ of symbols over some alphabet, usually all strings of a fixed length. Its directed links describe how this strings overlap if one of them is shifted. Here only shifts of a single cell are described.

There is a link from a source node ${\displaystyle w_{s}=a\alpha }$ to a drain node ${\displaystyle w_{d}=\beta b}$ if string ${\displaystyle w_{s}}$ overlap with string ${\displaystyle o_{R}}$ shifted right by one symbol. This means that the overlapping source substring ${\displaystyle \alpha }$ (${\displaystyle w_{s}}$ without the start symbol ${\displaystyle a}$) is equal to the overlapping drain substring ${\displaystyle \beta }$ (${\displaystyle w_{d}}$ without the end symbol ${\displaystyle b}$).

The topological matrix of the De Bruijn diagram is

${\displaystyle d_{w_{s}w_{d}}={\begin{cases}1,&\alpha =\beta \\0,&\alpha \neq \beta \end{cases}}}$

For the diagram to be easier to read and use on cellular automata this book uses a diagram representation, where all the nodes are drawn twice. Nodes on the left are source points of links and nodes on the right are drain points of links. The direction of the links is chosen to point in the increasing direction of cell position indexes.

• There is more about De Bruijn diagrams in references.

## Preimage diagrams and matrices

The overlapping of adjacent neighborhoods (dark gray)

The overlap ${\displaystyle o_{i}}$ is the group cells from the overlapping neighborhoods of a pair of adjacent cells ${\displaystyle c_{x}c_{x+1}}$. The size of the overlapping ${\displaystyle k-1}$ is one cell less than the size of the neighborhood.

${\displaystyle o_{x}=c_{x+1-k_{0}}c_{x+2-k_{0}}\dots c_{x+k-k_{0}-1}}$

A compact representation of the overlap is a number with ${\displaystyle k-1}$ digits base ${\displaystyle |S|}$.

${\displaystyle o_{x}=\sum _{i=0}^{k-2}{c_{x+1-k_{0}+i}|S|^{k-2+i}}=c_{x+1-k_{0}}|S|^{k-2}+c_{x+2-k_{0}}|S|^{k-2}+\dots +c_{x+k-k_{0}-1}|S|^{0}}$

If a cell sequence ${\displaystyle ...c_{x-2}c_{x-1}c_{x}c_{x+1}c_{x+2}c_{x+3}...}$ is cut (or joined) into two parts between ${\displaystyle c_{x}}$ and ${\displaystyle c_{x+1}}$, the neighborhood of the last cell in the left part ${\displaystyle ...c_{x-2}c_{x-1}c_{x}}$ is overlapping with the neighborhood of the first cell on the right part ${\displaystyle c_{x+1}c_{x+2}c_{x+3}...}$. The overlap ${\displaystyle o_{x}}$ at the cut (or junction) is defined as above and is used to describe the boundaries of sequences.

### Preimage matrix

The preimage diagram (described by the preimage matrix)

The first step to the preimage matrix is constructing a De Bruijn diagram representing preimages of a single cell in a cellular automaton. It's nodes are all ${\displaystyle |S|^{k-1}}$ different overlaps of neighborhoods. The source nodes ${\displaystyle o_{L}}$ are overlaps on the left side of the cell and the drain nodes ${\displaystyle o_{R}}$ are overlaps on the right side of the cell. The links represent neighborhoods ${\displaystyle n}$ and connect nodes ${\displaystyle o_{L}}$ and ${\displaystyle o_{R}}$ according to the next two decompositions:

• the neighborhood ${\displaystyle n=c_{L}o_{R}}$ is formed from the remaining left cell ${\displaystyle c_{L}}$ and the right overlap ${\displaystyle o_{R}}$ or
• the neighborhood ${\displaystyle n=o_{L}c_{R}}$ is formed from the left overlap ${\displaystyle o_{L}}$ and the remaining right cell ${\displaystyle c_{R}}$

The topological matrix of the diagram is a square of ${\displaystyle |S|^{k-1}\times |S|^{k-1}}$ elements.

${\displaystyle D=\left[{\begin{matrix}d_{00}&d_{01}&\cdots \\d_{10}&d_{11}&\cdots \\\vdots &\vdots &\ddots \end{matrix}}\right]}$

The value of an element is ${\displaystyle 1}$ if there is a link between nodes ${\displaystyle o_{L}o_{R}}$ and ${\displaystyle 0}$ else.

${\displaystyle d_{o_{L}o_{R}}={\begin{cases}1,&o_{L}c_{R}=c_{L}o_{R}=n\\0,&{\mbox{else}}\end{cases}}}$

The next step is to form a symbolic De Bruijn matrix, where elements are link labels. A link representing the neighborhood ${\displaystyle n}$ is labeled according to the output cell value ${\displaystyle c=f(n)}$ defined by the local transition function. Node pairs without a link can be labeled with a dot.

${\displaystyle d_{o_{L}o_{R}}={\begin{cases}f(n),&o_{L}c_{R}=c_{L}o_{R}=n\\.,&{\mbox{else}}\end{cases}}}$

The last step is to form preimage matrices ${\displaystyle D(c)}$ one for each of the ${\displaystyle |S|}$ available cell states ${\displaystyle c}$. There is a link between a pair of nodes ${\displaystyle o_{L}o_{R}}$ only if the relative neighborhood ${\displaystyle n}$ leads to the desired cell value ${\displaystyle c}$.

${\displaystyle d_{o_{L}o_{R}}(c)={\begin{cases}1,&o_{L}c_{R}=c_{L}o_{R}=n\wedge f(n)=c\\0,&{\mbox{else}}\end{cases}}}$

### The preimage matrix of a sequence

Before the definition of the preimage matrix can be extended to a sequence of cells ${\displaystyle \alpha }$ the meaning of the matrix elements must be defined, so the definition can be checked against it.

Entries ${\displaystyle d_{o_{L}o_{R}}}$ in the matrix ${\displaystyle D(\alpha )}$ represent the number of preimages of length ${\displaystyle |\alpha |+k-1}$ that begin with the left overlapping ${\displaystyle o_{L}}$ and end with the right overlapping ${\displaystyle o_{R}}$.

${\displaystyle \alpha ^{t-1}=o_{L}\beta _{R}=\beta _{L}o_{R}\;\wedge \;F(\alpha ^{t-1})=\alpha ^{t}\quad \Rightarrow \quad |F^{-1}(\alpha ^{t})|=d_{o_{L}o_{R}}(\alpha ^{t})}$

The preimage matrix of a string of cells ${\displaystyle \alpha =c_{p}c_{p+1}\dots c_{q}}$ is the multiplied chain of single cell matrices

${\displaystyle D(\alpha )=D(c_{p}c_{p+1}\dots c_{q})=\prod _{x=p}^{q}D(c_{x})=D(c_{p})\cdot D(c_{p+1})\cdots D(c_{q})}$

The preimage matrix of an empty string ${\displaystyle \varepsilon }$ is an identity matrix.

${\displaystyle D(\varepsilon )=I}$
${\displaystyle \Box }$

### Preimage boundary conditions

The preimage junction or boundary

The preimage vector consists of ${\displaystyle |S|^{k-1}}$ nonnegative integer entries, one for each of the possible neighborhood overlaps or nodes of the preimage diagram.

Elements ${\displaystyle p_{i}}$ of the preimage vector ${\displaystyle b_{x}}$ count the preimages that contain an overlap ${\displaystyle o_{x}=i}$ of value ${\displaystyle i}$ at position ${\displaystyle x}$ in the present cell sequence.

${\displaystyle b_{x}=[p_{0},p_{1},\dots ,p_{i-1},p_{i},p_{i+1},\dots ,p_{|S|^{k-1}-1}]}$

The preimage vector is used to describe the boundary or more precisely it can describe the preimage count at one side of a junction of two strings.

• to describe the right boundary of the string ${\displaystyle \alpha =\dots c_{x-1}c_{x}}$ the right boundary vector ${\displaystyle b_{R}}$ is used, it counts preimages to the right from the junction
• to describe the left boundary of the string ${\displaystyle \alpha =c_{x+1}c_{x+2}\dots }$ the left boundary vector ${\displaystyle b_{L}}$ is used, it counts preimages to the left from the junction

The unrestricted boundary is usually used to avoid any specific boundary. It is assumed that there is exactly one preimage for each overlap. All the entries in the vector are ${\displaystyle 1}$.

${\displaystyle b_{u}=[1,1,\dots ,1]\qquad |b_{u}|=|S|^{k-1}}$

Since there can be an infinite number of preimage for a semi-infinite sequence, usually only periodic sequences are used, counting only preimages of the period ${\displaystyle \alpha }$

${\displaystyle b_{L}=b_{u}D(\alpha )\,}$
${\displaystyle b_{R}=D(\alpha )b_{u}^{T}}$

Quiescent and ether backgrounds can be represented by periodic sequences.

### Counting preimages

The number of preimages ${\displaystyle p}$ (paths through the network) of a sequence ${\displaystyle \alpha }$ with the left boundary condition ${\displaystyle b_{L}}$ and the right boundary condition ${\displaystyle b_{R}}$ is defined as

${\displaystyle p=b_{L}D(\alpha )b_{R}^{T}}$

The unrestricted boundary is commonly used and it counts all the preimages of a sequence ${\displaystyle D(\alpha )}$ exactly ones. The number of preimages is simply the sum of all elements in the preimage matrix ${\displaystyle D(\alpha )}$.

${\displaystyle p=b_{u}D(\alpha )b_{u}^{T}\,}$

#### Preimages of a cyclic string of cells

Since a string in a cyclic lattice must have the same overlapping at its left and right side, only elements on the diagonal of the De Bruijn matrix form valid preimages. The number of all preimages of a string ${\displaystyle \alpha }$ is the sum of elements on the diagonal.

${\displaystyle p=\sum _{i=0}^{|S|^{k-1}}d_{ii}(\alpha )}$

#### Garden of eden

A garden of eden sequence does not have preimages. For finite strings on an infinite lattice this is true exactly when the De Bruijn matrix of the string is a zero matrix ${\displaystyle M_{0}}$ (all elements are zero).

${\displaystyle D(\alpha )=M_{0}\Rightarrow \alpha \in G}$

Any string which substring is a garden of eden is a garden of eden.

${\displaystyle \forall \beta _{L},\beta _{R}\;[\alpha \in G\Rightarrow \beta _{L}\alpha \beta _{R}\in G]}$

A garden of eden can be the consequence of the boundary conditions, both restricted of cyclic boundaries.

## Proofs

### Proof of the preimage matrix equation for sequences

The proof of the formula on sequences is an induction on the length of the string.

Base (${\displaystyle l=0,1}$)
If the length of the string is ${\displaystyle 0}$ than there is no shift and nodes are linked only to themselves.
For the string of length ${\displaystyle 1}$ the meaning of the single cell preimage matrix elements is evident from the definition.
Induction
${\displaystyle D(\alpha a)=D(\alpha )D(a)\,}$

## References

1. Harold V. McIntosh, Linear Cellular Automata Via de Bruijn Diagrams, August 10, 1991 (HTML, PDF)
2. Harold V. McIntosh, Ancestors: Commentaries on The Global Dynamics of Cellular Automata by Andrew Wuensche and Mike Lesser (Addison-Wesley, 1992), July 20, 1993 (HTML, PDF)
3. Erica Jen, Enumeration of Preimages in Cellular Automata, Complex Systems 3 (5) (1989) 421-456
4. Burton Voorhees, Predecessors of cellular automata states II. Pre-images of finite sequences, Phisica D 73 (1-2) (1994) 136-151
5. Iztok Jeras, Andrej Dobnikar Algorithms for computing preimages of cellular automata configurations PDF

## Software

1. DDLab Tools for researching Cellular Automata, Random Boolean Networks, multi-value Discrete Dynamical Networks, and beyond; by Andy Wuensche.
2. Iztok Jeras, Algorithms for computing preimages of cellular automata configurations TAR.BZ2
3. Cellular Automata Pre-Image Generator CAPIG is a user-friendly free software made to find pre-images according to the user chosen configuration.