Cellular Automata/Boundary Conditions

On bounded lattices the information about preimages outside the boundaries of the observed string α can be described by two boundary preimage vectors (left b_L and right b_R). The observed string α can be seen as part of an infinite string β_Lαβ_R. Boundary vector b_L describes preimages of the semi-infinite string β_L and boundary vector b_R describes preimages of the semi-infinite string β_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 β_L and β_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.