Cellular Automata/Boundary Conditions

On bounded lattices the information about preimages outside the boundaries of the observed string $\alpha$ can be described by two boundary preimage vectors (left $b_L$ and right $b_R$). The observed string $\alpha$ can be seen as part of an infinite string $\beta_L \alpha \beta_R$. Boundary vector $b_L$ describes preimages of the semi-infinite string $\beta_L$ and boundary vector $b_R$ describes preimages of the semi-infinite string $\beta_R$. Vector elements are the numbers of preimages that can be traced from the boundary to infinity for each of the overlaps at the boundaries. Element at position $o_L$ in the left boundary vector $b_L$ specifies the number of preimages $p_{-\infty \leftrightarrow o_L}(\beta_L)$ that can be traced from left infinity to the overlap $o_L$ at the left boundary of the observed string. The definition of the right boundary vector $b_R$ is similar.

$b_L = [ p_{-\infty \leftrightarrow o_L=0}, p_{-\infty \leftrightarrow o_L=1}, \dots, p_{-\infty \leftrightarrow o_L}, \dots, p_{-\infty \leftrightarrow o_L=k^{m-1}-1} ]^T$

$b_R = [ p_{0=o_R \leftrightarrow +\infty}, p_{1=o_R \leftrightarrow +\infty}, \dots, p_{o_R \leftrightarrow +\infty}, \dots, p_{k^{m-1}-1=o_R \leftrightarrow +\infty} ]^T$

Since we usually don't care about the state of the CA outside the observed string, unrestricted boundary vectors can be used. \paragraph{Definition} For the \emph{unrestricted boundary vector} it is assumed that each of the boundary overlaps can be used to trace exactly one path to infinity. Therefore the unrestricted boundary vector contains all ones.

$b_u = [1,1,\dots,1]^T$

Note The below definitions rely on assumptions that are not proved yet, so the definitions my be wrong.

General boundary vectors $b_L$ and $b_R$ describe general infinite strings $\beta_L$ and $\beta_R$. It is assumed that this strings end with an unrestricted boundary vector $b_u$ in the infinity.

$b_L^T = \lim_{|\beta_L|\rightarrow\infty} b_u^T \, D(\beta_L) \qquad b_R = \lim_{|\beta_R|\rightarrow\infty} D(\beta_R) \, b_u$

Since an infinite string can have an infinite number of preimages, this definition is rarely useful. Boolean values can be used instead of integers to state if the overlap can be used for tracing or not. The equations are identical, only the scalar multiplication operator used for matrix multiplication is replaced by an XOR logical operation. Another option is using probabilities.

Another common boundary is an infinite periodic string with a finite period. Some commonly used boundaries can be defined this way. The periodic boundary vectors $b_{\bar{L}}$ and $b_{\bar{R}}$ describe infinite periodic strings with finite periods $\overline{\beta_L}$ and $\overline{\beta_R}$. This strings end with the same boundary vector $b_{\bar{L}}$ and $b_{\bar{R}}$ in the infinity. The preimage matrix of a sting of $n$ period strings $\overline{\beta}^n$ is computed as $D(\overline{\beta}^n)=D^n(\overline{\beta})$.

$b_{\bar{L}}^T = \lim_{n\rightarrow\infty} b_{\bar{L}}^T \, D^n(\overline{\beta_L}) \qquad b_{\bar{R}} = \lim_{n\rightarrow\infty} D^n(\overline{\beta_R}) \, b_{\bar{R}}$

The problem with this definition is thet there may by many different vectors that fulfil the criteria. There is an example of periodic boundaries with a finite number of preimages at the end of the paper.